Add pass to turn function into Unreachable and script to find UB. (WIP)

[fhahn]

Summary

This adds a pass to replace function bodies with 'unreachable' and a
script that checks if the result still verifies.

This can be used to find functions in llvm-lit tests that have
unconditional UB using

llvm-lit -j4 -sv -Dopt=~/find-ub-in-test.sh

Examples of found & fixed UB:

• b8d728a098b1
• 684a82fbc543

llvm/include/llvm/Transforms/Scalar/ToUnreachable.h

+//===- ToUnreachable.h - Turn function into unreachable. --------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_SCALAR_TOUNREACHABLE_H
+#define LLVM_TRANSFORMS_SCALAR_TOUNREACHABLE_H
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+struct ToUnreachablePass : public PassInfoMixin<ToUnreachablePass> {
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+} // namespace llvm
+
+#endif

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h"
 #include "llvm/Transforms/Scalar/SimplifyCFG.h"
 #include "llvm/Transforms/Scalar/Sink.h"
 #include "llvm/Transforms/Scalar/SpeculativeExecution.h"
 #include "llvm/Transforms/Scalar/StraightLineStrengthReduce.h"
 #include "llvm/Transforms/Scalar/StructurizeCFG.h"
 #include "llvm/Transforms/Scalar/TLSVariableHoist.h"
 #include "llvm/Transforms/Scalar/TailRecursionElimination.h"
+#include "llvm/Transforms/Scalar/ToUnreachable.h"
 #include "llvm/Transforms/Scalar/WarnMissedTransforms.h"
 #include "llvm/Transforms/Utils/AddDiscriminators.h"
 #include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
 #include "llvm/Transforms/Utils/BreakCriticalEdges.h"
 #include "llvm/Transforms/Utils/CanonicalizeAliases.h"
 #include "llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h"
 #include "llvm/Transforms/Utils/Debugify.h"
 #include "llvm/Transforms/Utils/EntryExitInstrumenter.h"

llvm/lib/Passes/PassRegistry.def

 FUNCTION_PASS("verify<regions>", RegionInfoVerifierPass())
 FUNCTION_PASS("verify<safepoint-ir>", SafepointIRVerifierPass())
 FUNCTION_PASS("verify<scalar-evolution>", ScalarEvolutionVerifierPass())
 FUNCTION_PASS("view-cfg", CFGViewerPass())
 FUNCTION_PASS("view-cfg-only", CFGOnlyViewerPass())
 FUNCTION_PASS("tlshoist", TLSVariableHoistPass())
 FUNCTION_PASS("transform-warning", WarnMissedTransformationsPass())
 FUNCTION_PASS("tsan", ThreadSanitizerPass())
+FUNCTION_PASS("to-unreachable", ToUnreachablePass())
 FUNCTION_PASS("memprof", MemProfilerPass())
 #undef FUNCTION_PASS
 
 #ifndef FUNCTION_PASS_WITH_PARAMS
 #define FUNCTION_PASS_WITH_PARAMS(NAME, CLASS, CREATE_PASS, PARSER, PARAMS)
 #endif
 FUNCTION_PASS_WITH_PARAMS("early-cse",
                           "EarlyCSEPass",

llvm/lib/Transforms/Scalar/CMakeLists.txt

add_llvm_component_library(LLVMScalarOpts
   SimpleLoopUnswitch.cpp
   SimplifyCFGPass.cpp
   Sink.cpp
   SpeculativeExecution.cpp
   StraightLineStrengthReduce.cpp
   StructurizeCFG.cpp
   TailRecursionElimination.cpp
   TLSVariableHoist.cpp
+  ToUnreachable.cpp
   WarnMissedTransforms.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms/Scalar
 
   DEPENDS
   intrinsics_gen

llvm/lib/Transforms/Scalar/ToUnreachable.cpp

+//===- ToUnreachable.cpp - Turn function into unreachable. ------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Scalar/ToUnreachable.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+
+using namespace llvm;
+
+PreservedAnalyses ToUnreachablePass::run(Function &F,
+                                         FunctionAnalysisManager &AM) {
+  SmallVector<BasicBlock *> AllBlocks;
+  for (BasicBlock &BB : F) {
+    AllBlocks.push_back(&BB);
+    BB.dropAllReferences();
+  }
+
+  for (unsigned I = 1; I < AllBlocks.size(); ++I) {
+    AllBlocks[I]->eraseFromParent();
+  }
+
+  for (Instruction &I : make_early_inc_range(*AllBlocks[0])) {
+    I.eraseFromParent();
+  }
+
+  new UnreachableInst(F.getContext(), AllBlocks[0]);
+  return PreservedAnalyses::none();
+}

llvm/utils/find-ub-in-test.sh

+#!/bin/bash
+
+FILE=""
+S_OPT=""
+ORIG_ARGS="$@"
+for arg in $@; do
+  shift
+  if [[ $arg == *".ll" ]]; then
+      FILE="${arg}"
+  fi
+done
+
+if [[ "$OSTYPE" == "darwin"* ]]; then
+  # Mac
+  TV_SHAREDLIB=tv.dylib
+else
+  # Linux, Cygwin/Msys, or Win32?
+  TV_SHAREDLIB=tv.so
+fi
+
+TV_REPORT_DIR=""
+TIMEOUT=""
+TV_SMT_TO=""
+TV_SMT_STATS=""
+TV_REPORT_DIR=-tv-report-dir=alive2/build/logs
+TIMEOUT=""
+TV_SMT_TO="-tv-smt-to=100000"
+TV_SMT_STATS=-tv-smt-stats
+
+NPM_PLUGIN="-load-pass-plugin=alive2/build/tv/$TV_SHAREDLIB"
+
+# Write input to temporary file so it can be passed to multiple opt calls, even
+# if read from stdin. Run opt with original args, save output.
+OUT=$(mktemp)
+if [[ $FILE == "" ]]; then
+    FILE="$(mktemp)"
+    bin/opt > $FILE
+    bin/opt $ORIG_ARGS $FILE > $OUT
+else
+  bin/opt $ORIG_ARGS > $OUT
+fi
+
+# Check if replacing all input functions with unreachable still verifies. If it does, the input has likely unconditional UB.
+bin/opt -load=live2/build/tv/$TV_SHAREDLIB  $NPM_PLUGIN -tv-exit-on-error -passes="tv,to-unreachable,tv" -disable-output $FILE $TV_SMT_TO $TV_REPORT_DIR $TV_SMT_STATS 2> /dev/null
+ret=$?
+
+cat $OUT
+
+if [ $ret -ne 0 ]; then
+    exit 0
+fi
+exit 1