workaround for LLVM PR39177

provides a workaround for LLVM bug PR39177, which affects LLVM
versions 3.9 - 7.0.0: https://bugs.llvm.org/show_bug.cgi?id=39177

This commit is intended to be reverted once support for LLVM
versions <= 7 is dropped from KLEE.

8 files changed, 281 insertions, 1 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 3a41d0f3..164ce1a1 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -496,6 +496,11 @@ else()
 endif()
 
 ################################################################################
+# Workarounds
+################################################################################
+include(${CMAKE_SOURCE_DIR}/cmake/workaround_llvm_pr39177.cmake)
+
+################################################################################
 # Global clean target
 ################################################################################
 # CMake already uses the "clean" target name but it doesn't clean everything
diff --git a/cmake/workaround_llvm_pr39177.cmake b/cmake/workaround_llvm_pr39177.cmake
new file mode 100644
index 00000000..317cac7e
--- /dev/null
+++ b/cmake/workaround_llvm_pr39177.cmake
@@ -0,0 +1,134 @@
+# Workaround for LLVM PR39177
+#  - https://bugs.llvm.org/show_bug.cgi?id=39177
+#  - https://github.com/klee/klee/issues/1000
+#
+# TODO: remove when support for LLVM <= 7 is dropped
+#
+# Short description of the bug:
+# The LLVM pass `-instcombine` optimizes calls to C standard lib functions by,
+# e.g. transforming the following call to a call to fwrite():
+#   fprintf(stderr, "hello world!\n");
+# In uClibc, and thus klee-uclibc, fwrite() is defined as an alias to a function
+# fwrite_unlocked(). This translates to a GlobalAlias in LLVM IR. When trying to
+# infer function attributes from fwrite(), LLVM tries to cast a GlobalAlias to a
+# Function, which results in a null-pointer dereference. When calling KLEE with
+# `-optimize`, this leads to a crash of KLEE.
+#
+# This bug affects LLVM 3.9 - 7.0.0.
+#
+# As the bug results in a null-pointer dereference when trying to access a
+# Function that is only available as GlobalAlias, this workaround introduces a
+# pass into KLEE that replaces aliases for certain C standard lib function with
+# clones of the corresponding aliasee function.
+#
+# The bug was fixed in the following commits in LLVM:
+#  - https://reviews.llvm.org/rL344454
+#  - https://reviews.llvm.org/rL344455
+#  - https://reviews.llvm.org/rL344645
+# These patches were then applied to the release_70 branch to land in 7.0.1:
+#  - https://reviews.llvm.org/rL345921
+#
+# This CMake file checks whether the method responsible for the null-pointer
+# dereference leads to a crash of the program given in this file.
+#
+# Files that were created/modified for this workaround:
+# [NEW FILE] cmake/workaround_llvm_pr39177.cmake (this file)
+# [NEW FILE] cmake/workaround_llvm_pr39177.ll (auxiliary file for feature test)
+# [NEW FILE] lib/Module/WorkaroundLLVMPR39177.cpp
+#
+# [MODIFIED] CMakeLists.txt (including this file)
+# [MODIFIED] include/klee/Config/config.h.cmin (cmakedefine)
+# [MODIFIED] lib/Module/CMakeLists.txt
+# [MODIFIED] lib/Module/Optimize.cpp (add pass during optimization)
+# [MODIFIED] lib/Module/Passes.h
+
+# Detect whether LLVM version is affected by PR39177
+if ((${LLVM_VERSION_MAJOR} GREATER 3 OR (${LLVM_VERSION_MAJOR} EQUAL 3 AND ${LLVM_VERSION_MINOR} EQUAL 9)) # LLVM >= 3.9
+   AND (${LLVM_VERSION_MAJOR} LESS 7 OR (${LLVM_VERSION_MAJOR} EQUAL 7 AND ${LLVM_VERSION_MINOR} EQUAL 0 AND ${LLVM_VERSION_PATCH} EQUAL 0))) # LLVM <= 7.0.0
+  set(DISABLE_WORKAROUND_LLVM_PR39177_DEFAULT OFF)
+else()
+  set(DISABLE_WORKAROUND_LLVM_PR39177_DEFAULT ON)
+endif()
+
+option(DISABLE_WORKAROUND_LLVM_PR39177 "Disable Workaround for LLVM PR39177 (affecting LLVM 3.9 - 7.0.0)" ${DISABLE_WORKAROUND_LLVM_PR39177_DEFAULT})
+
+if (NOT DISABLE_WORKAROUND_LLVM_PR39177)
+  # Detect whether PR39177 leads to crash
+  include(CheckCXXSourceRuns)
+
+  cmake_push_check_state()
+  klee_get_llvm_libs(LLVM_LIBS asmparser transformutils)
+  set(CMAKE_REQUIRED_INCLUDES "${LLVM_INCLUDE_DIRS}")
+  set(CMAKE_REQUIRED_LIBRARIES "${LLVM_LIBS}")
+
+  check_cxx_source_runs("
+    #include \"llvm/Analysis/TargetLibraryInfo.h\"
+    #include \"llvm/AsmParser/Parser.h\"
+    #include \"llvm/AsmParser/SlotMapping.h\"
+    #include \"llvm/IR/ConstantFolder.h\"
+    #include \"llvm/IR/Constants.h\"
+    #include \"llvm/IR/DataLayout.h\"
+    #include \"llvm/IR/DiagnosticInfo.h\"
+    #include \"llvm/IR/Instructions.h\"
+    #include \"llvm/IR/IRBuilder.h\"
+    #include \"llvm/IR/LLVMContext.h\"
+    #include \"llvm/Transforms/Utils/BuildLibCalls.h\"
+
+    #include <signal.h>
+
+    void handler(int, siginfo_t*, void*) {
+      // program received SIGSEGV
+      exit(1);
+    }
+
+    using namespace llvm;
+
+    int main() {
+      // capture segfault
+      struct sigaction action;
+      memset(&action, 0, sizeof(struct sigaction));
+      action.sa_flags = SA_SIGINFO;
+      action.sa_sigaction = handler;
+      sigaction(SIGSEGV, &action, NULL);
+
+      // setup test
+      LLVMContext Ctx;
+      SMDiagnostic Error;
+      SlotMapping Mapping;
+      auto M = llvm::parseAssemblyFile(\"${CMAKE_SOURCE_DIR}/cmake/workaround_llvm_pr39177.ll\", Error, Ctx, &Mapping);
+      if (!M) {
+        Error.print(\"AssemblyString\", llvm::errs());
+        return -1;
+      }
+
+      auto *F = M->getFunction(\"test\");
+      auto *CI = cast<CallInst>(&*std::next(F->begin()->begin()));
+      auto &DL = M->getDataLayout();
+      Value *Size = ConstantInt::get(DL.getIntPtrType(Ctx), 8);
+      ConstantFolder CF;
+      IRBuilder<> B(&*F->begin(), CF);
+      TargetLibraryInfo TLI = TargetLibraryInfoWrapperPass({\"x86_64\", \"\", \"linux-gnu\"}).getTLI();
+
+      // test if this call produces segfault
+      emitFWrite(CI->getArgOperand(1), Size, CI->getArgOperand(0), B, DL, &TLI);
+
+      return 0;
+    }"
+    LLVM_PR39177_FIXED
+  )
+  cmake_pop_check_state()
+
+  if (NOT LLVM_PR39177_FIXED)
+    message(STATUS "Workaround for LLVM PR39177 (affecting LLVM 3.9 - 7.0.0) enabled")
+    set(USE_WORKAROUND_LLVM_PR39177 1) # For config.h
+  else()
+    message(FATAL_ERROR "DISABLE_WORKAROUND_LLVM_PR39177 is not set to true"
+      "but crash resulting from PR39177 could not be detected."
+      "You may try to disable the workaround using"
+      "-DDISABLE_WORKAROUND_LLVM_PR39177=1 if you believe the issue is patched"
+      "in your version of LLVM.")
+  endif()
+else()
+  message(STATUS "Workaround for LLVM PR39177 (affecting LLVM 3.9 - 7.0.0) disabled")
+  unset(USE_WORKAROUND_LLVM_PR39177) # For config.h
+endif()
diff --git a/cmake/workaround_llvm_pr39177.ll b/cmake/workaround_llvm_pr39177.ll
new file mode 100644
index 00000000..ebca4f1c
--- /dev/null
+++ b/cmake/workaround_llvm_pr39177.ll
@@ -0,0 +1,18 @@
+%struct._IO_FILE = type { i32, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, %struct._IO_marker*, %struct._IO_FILE*, i32, i32, i64, i16, i8, [1 x i8], i8*, i64, i8*, i8*, i8*, i8*, i64, i32, [20 x i8] }
+%struct._IO_marker = type { %struct._IO_marker*, %struct._IO_FILE*, i32 }
+
+@stdout = external global %struct._IO_FILE*, align 8
+@.str = private unnamed_addr constant [11 x i8] c"abcdefgh!\0A\00", align 1
+@fwrite = alias i64 (i8*, i64, i64, %struct._IO_FILE*), i64 (i8*, i64, i64, %struct._IO_FILE*)* @__fwrite_alias
+
+define i64 @__fwrite_alias(i8*, i64, i64, %struct._IO_FILE*) {
+  ret i64 0
+}
+
+define void @test() {
+  %1 = load %struct._IO_FILE*, %struct._IO_FILE** @stdout, align 8
+  %2 = call i32 (%struct._IO_FILE*, i8*, ...) @fprintf(%struct._IO_FILE* %1, i8* getelementptr inbounds ([11 x i8], [11 x i8]* @.str, i32 0, i32 0))
+  ret void
+}
+
+declare i32 @fprintf(%struct._IO_FILE*, i8*, ...)
diff --git a/include/klee/Config/config.h.cmin b/include/klee/Config/config.h.cmin
index 0a5811b7..a7890fe7 100644
--- a/include/klee/Config/config.h.cmin
+++ b/include/klee/Config/config.h.cmin
@@ -80,6 +80,9 @@
 /* Define to the version of this package. */
 #cmakedefine PACKAGE_VERSION @PACKAGE_VERSION@
 
+/* Use Workaround for LLVM PR39177 (affecting LLVM 3.9 - 7.0.0) */
+#cmakedefine USE_WORKAROUND_LLVM_PR39177 @USE_WORKAROUND_LLVM_PR39177@
+
 /* klee-uclibc is supported */
 #cmakedefine SUPPORT_KLEE_UCLIBC @SUPPORT_KLEE_UCLIBC@
 
diff --git a/lib/Module/CMakeLists.txt b/lib/Module/CMakeLists.txt
index 4347b67d..73f003c2 100644
--- a/lib/Module/CMakeLists.txt
+++ b/lib/Module/CMakeLists.txt
@@ -6,7 +6,7 @@
 # License. See LICENSE.TXT for details.
 #
 #===------------------------------------------------------------------------===#
-klee_add_component(kleeModule
+set(KLEE_MODULE_COMPONENT_SRCS
   Checks.cpp
   InstructionInfoTable.cpp
   InstructionOperandTypeCheckPass.cpp
@@ -21,6 +21,14 @@ klee_add_component(kleeModule
   Scalarizer.cpp
 )
 
+if (USE_WORKAROUND_LLVM_PR39177)
+  list(APPEND KLEE_MODULE_COMPONENT_SRCS WorkaroundLLVMPR39177.cpp)
+endif()
+
+klee_add_component(kleeModule
+  ${KLEE_MODULE_COMPONENT_SRCS}
+)
+
 set(LLVM_COMPONENTS
   bitreader
   bitwriter
diff --git a/lib/Module/Optimize.cpp b/lib/Module/Optimize.cpp
index 627921cb..e0a8fc41 100644
--- a/lib/Module/Optimize.cpp
+++ b/lib/Module/Optimize.cpp
@@ -18,6 +18,10 @@
 #include "klee/Config/Version.h"
 #include "klee/Internal/Module/LLVMPassManager.h"
 
+#ifdef USE_WORKAROUND_LLVM_PR39177
+#include "Passes.h"
+#endif
+
 #include "llvm/Analysis/Passes.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/IR/Module.h"
@@ -180,6 +184,10 @@ void Optimize(Module *M, llvm::ArrayRef<const char *> preservedFunctions) {
   if (VerifyEach)
     Passes.add(createVerifierPass());
 
+#ifdef USE_WORKAROUND_LLVM_PR39177
+  addPass(Passes, new klee::WorkaroundLLVMPR39177Pass());
+#endif
+
   // Add an appropriate DataLayout instance for this module...
 #if LLVM_VERSION_CODE >= LLVM_VERSION(3, 7)
   // LLVM 3.7+ doesn't have DataLayoutPass anymore.
diff --git a/lib/Module/Passes.h b/lib/Module/Passes.h
index 9d39e8f2..417ebe7d 100644
--- a/lib/Module/Passes.h
+++ b/lib/Module/Passes.h
@@ -173,6 +173,18 @@ public:
   bool runOnModule(llvm::Module &M) override;
   bool checkPassed() const { return instructionOperandsConform; }
 };
+
+#ifdef USE_WORKAROUND_LLVM_PR39177
+/// WorkaroundLLVMPR39177Pass - Workaround for LLVM PR39177 within KLEE repo.
+/// For more information on this, please refer to the comments in
+/// cmake/workaround_llvm_pr39177.cmake
+class WorkaroundLLVMPR39177Pass : public llvm::ModulePass {
+public:
+  static char ID;
+  WorkaroundLLVMPR39177Pass() : llvm::ModulePass(ID) {}
+  bool runOnModule(llvm::Module &M) override;
+};
+#endif
 } // namespace klee
 
 #endif
diff --git a/lib/Module/WorkaroundLLVMPR39177.cpp b/lib/Module/WorkaroundLLVMPR39177.cpp
new file mode 100644
index 00000000..23eeb932
--- /dev/null
+++ b/lib/Module/WorkaroundLLVMPR39177.cpp
@@ -0,0 +1,92 @@
+//===-- WorkaroundLLVMPR39177.cpp -------------------------------*- C++ -*-===//
+//
+//                     The KLEE Symbolic Virtual Machine
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// This pass provides a workaround for LLVM bug PR39177 within the KLEE repo.
+// For more information on this, please refer to the comments in
+// cmake/workaround_llvm_pr39177.cmake
+
+#include "Passes.h"
+#include "klee/Internal/Support/ErrorHandling.h"
+
+#include "llvm/Transforms/Utils/Cloning.h"
+
+using namespace llvm;
+
+namespace klee {
+
+bool WorkaroundLLVMPR39177Pass::runOnModule(Module &M) {
+  bool modified = false;
+
+  const char *libfunctions[] = {
+    "strlen",
+    "strchr",
+    "strncmp",
+    "strcpy",
+    "strncpy",
+    "__memcpy_chk",
+    "memchr",
+    "memcmp",
+    "putchar",
+    "puts",
+    "fputc",
+    "fputc_unlocked",
+    "fputs",
+    "fputs_unlocked",
+    "fwrite",
+    "malloc",
+    "calloc",
+    "fwrite_unlocked",
+    "fgetc_unlocked",
+    "fgets_unlocked",
+    "fread_unlocked",
+    "memset_pattern16",
+    "fopen"
+  };
+
+  for (auto *funcname : libfunctions) {
+    if (M.getFunction(funcname) != nullptr)
+      continue;
+
+    GlobalValue *gv = M.getNamedValue(funcname);
+    auto *alias = dyn_cast_or_null<GlobalAlias>(gv);
+    if (alias == nullptr)
+      continue;
+
+    // get aliasee function if exists
+    while (auto *ga = dyn_cast<GlobalAlias>(alias->getAliasee())) {
+      assert(ga != alias && "alias pointing to itself");
+      alias = ga;
+    }
+    Function *f = dyn_cast<Function>(alias->getAliasee());
+    if (f == nullptr)
+      continue;
+
+    std::string aliasName = alias->getName().str();
+
+    // clone function
+    ValueToValueMapTy VMap;
+    Function *g = CloneFunction(f, VMap);
+
+    // replace alias with cloned function
+    alias->replaceAllUsesWith(g);
+    g->takeName(alias);
+    alias->eraseFromParent();
+
+    klee_message(
+        "WorkaroundLLVMPR39177: replaced alias @%s with clone of function @%s",
+        aliasName.c_str(), f->getName().str().c_str());
+    modified = true;
+  }
+
+  return modified;
+}
+
+char WorkaroundLLVMPR39177Pass::ID = 0;
+
+} // namespace klee