implement FunctionAliasPass

7 files changed, 444 insertions, 0 deletions

diff --git a/lib/Module/CMakeLists.txt b/lib/Module/CMakeLists.txt
index 5f234237..f78575fb 100644
--- a/lib/Module/CMakeLists.txt
+++ b/lib/Module/CMakeLists.txt
@@ -8,6 +8,7 @@
 #===------------------------------------------------------------------------===#
 set(KLEE_MODULE_COMPONENT_SRCS
   Checks.cpp
+  FunctionAlias.cpp
   InstructionInfoTable.cpp
   InstructionOperandTypeCheckPass.cpp
   IntrinsicCleaner.cpp
diff --git a/lib/Module/FunctionAlias.cpp b/lib/Module/FunctionAlias.cpp
new file mode 100644
index 00000000..83b763f7
--- /dev/null
+++ b/lib/Module/FunctionAlias.cpp
@@ -0,0 +1,246 @@
+//===-- FunctionAliasPass.cpp -----------------------------------*- C++ -*-===//
+//
+//                     The KLEE Symbolic Virtual Machine
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Passes.h"
+#include "klee/Internal/Support/ErrorHandling.h"
+#include "klee/OptionCategories.h"
+
+#include "llvm/IR/GlobalAlias.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Regex.h"
+
+using namespace llvm;
+
+namespace {
+
+cl::list<std::string>
+    FunctionAlias("function-alias",
+                  cl::desc("Replace functions that match name or regular "
+                           "expression pattern with an alias to the function "
+                           "whose name is given by replacement"),
+                  cl::value_desc("name|pattern>:<replacement"),
+                  cl::cat(klee::ModuleCat));
+
+} // namespace
+
+namespace klee {
+
+bool FunctionAliasPass::runOnModule(Module &M) {
+  bool modified = false;
+
+#if LLVM_VERSION_CODE >= LLVM_VERSION(3, 9)
+  assert((M.ifunc_size() == 0) && "Unexpected ifunc");
+#endif
+
+  for (const auto &pair : FunctionAlias) {
+    bool matchFound = false;
+
+    // regex pattern can contain colons, e.g. in character classes,
+    // but replacement function name cannot
+    std::size_t lastColon = pair.rfind(':');
+    if (lastColon == std::string::npos) {
+      klee_error("function-alias: no replacement given");
+    }
+    std::string pattern = pair.substr(0, lastColon);
+    std::string replacement = pair.substr(lastColon + 1);
+
+    if (pattern.empty())
+      klee_error("function-alias: name or pattern cannot be empty");
+    if (replacement.empty())
+      klee_error("function-alias: replacement cannot be empty");
+
+    if (pattern == replacement) {
+      klee_error("function-alias: @%s cannot replace itself", pattern.c_str());
+    }
+
+    // check if replacement function exists
+    GlobalValue *replacementValue = M.getNamedValue(replacement);
+    if (!isFunctionOrGlobalFunctionAlias(replacementValue))
+      klee_error("function-alias: replacement function @%s could not be found",
+                 replacement.c_str());
+
+    // directly replace if pattern is not a regex
+    GlobalValue *match = M.getNamedValue(pattern);
+    if (isFunctionOrGlobalFunctionAlias(match)) {
+      if (tryToReplace(match, replacementValue)) {
+        modified = true;
+        klee_message("function-alias: replaced @%s with @%s", pattern.c_str(),
+                     replacement.c_str());
+        continue;
+      }
+    }
+    if (match != nullptr) {
+      // pattern is not a regex, but no replacement was found
+      klee_error("function-alias: no (replacable) match for '%s' found",
+                 pattern.c_str());
+    }
+
+    Regex regex(pattern);
+    std::string error;
+    if (!regex.isValid(error)) {
+      klee_error("function-alias: '%s' is not a valid regex: %s",
+                 pattern.c_str(), error.c_str());
+    }
+
+    std::vector<GlobalValue *> matches;
+
+    // find matches for regex
+#if LLVM_VERSION_CODE >= LLVM_VERSION(5, 0)
+    for (GlobalValue &global : M.global_values()) {
+#else
+    // chain iterators of alias list and function list
+    auto firstIt = M.getAliasList().begin();
+    auto firstIe = M.getAliasList().end();
+    auto secondIt = M.getFunctionList().begin();
+    auto secondIe = M.getFunctionList().end();
+    for (bool firstList = true;;
+         (firstList && (++firstIt != firstIe)) || (++secondIt != secondIe)) {
+      GlobalValue *gv = nullptr;
+      if (firstIt == firstIe)
+        firstList = false;
+      if (firstList) {
+        gv = cast<GlobalValue>(&*firstIt);
+      } else {
+        if (secondIt == secondIe)
+          break;
+        gv = cast<GlobalValue>(&*secondIt);
+      }
+      GlobalValue &global = *gv;
+#endif
+      if (!global.hasName())
+        continue;
+
+      if (!isFunctionOrGlobalFunctionAlias(&global))
+        continue;
+
+      SmallVector<StringRef, 8> matchVec;
+      bool match = regex.match(global.getName(), &matchVec);
+      if (match && matchVec[0].str() == global.getName().str()) {
+        if (global.getName().str() == replacement) {
+          klee_warning("function-alias: do not replace @%s (matching '%s') "
+                       "with @%s: cannot replace itself",
+                       global.getName().str().c_str(), pattern.c_str(),
+                       replacement.c_str());
+          continue;
+        }
+        matches.push_back(&global);
+      }
+    }
+
+    // replace all found regex matches
+    for (GlobalValue *global : matches) {
+      // name will be invalidated by tryToReplace
+      std::string name = global->getName().str();
+      if (tryToReplace(global, replacementValue)) {
+        modified = true;
+        matchFound = true;
+        klee_message("function-alias: replaced @%s (matching '%s') with @%s",
+                     name.c_str(), pattern.c_str(), replacement.c_str());
+      }
+    }
+
+    if (!matchFound) {
+      klee_error("function-alias: no (replacable) match for '%s' found",
+                 pattern.c_str());
+    }
+  }
+
+  return modified;
+}
+
+const FunctionType *FunctionAliasPass::getFunctionType(const GlobalValue *gv) {
+  const Type *type = gv->getType();
+  while (type->isPointerTy()) {
+    const PointerType *ptr = cast<PointerType>(type);
+    type = ptr->getElementType();
+  }
+  return cast<FunctionType>(type);
+}
+
+bool FunctionAliasPass::checkType(const GlobalValue *match,
+                                  const GlobalValue *replacement) {
+  const FunctionType *MFT = getFunctionType(match);
+  const FunctionType *RFT = getFunctionType(replacement);
+  assert(MFT != nullptr && RFT != nullptr);
+
+  if (MFT->getReturnType() != RFT->getReturnType()) {
+    klee_warning("function-alias: @%s could not be replaced with @%s: "
+                 "return type differs",
+                 match->getName().str().c_str(),
+                 replacement->getName().str().c_str());
+    return false;
+  }
+
+  if (MFT->isVarArg() != RFT->isVarArg()) {
+    klee_warning("function-alias: @%s could not be replaced with @%s: "
+                 "one has varargs while the other does not",
+                 match->getName().str().c_str(),
+                 replacement->getName().str().c_str());
+    return false;
+  }
+
+  if (MFT->getNumParams() != RFT->getNumParams()) {
+    klee_warning("function-alias: @%s could not be replaced with @%s: "
+                 "number of parameters differs",
+                 match->getName().str().c_str(),
+                 replacement->getName().str().c_str());
+    return false;
+  }
+
+  std::size_t numParams = MFT->getNumParams();
+  for (std::size_t i = 0; i < numParams; ++i) {
+    if (MFT->getParamType(i) != RFT->getParamType(i)) {
+      klee_warning("function-alias: @%s could not be replaced with @%s: "
+                   "parameter types differ",
+                   match->getName().str().c_str(),
+                   replacement->getName().str().c_str());
+      return false;
+    }
+  }
+  return true;
+}
+
+bool FunctionAliasPass::tryToReplace(GlobalValue *match,
+                                     GlobalValue *replacement) {
+  if (!checkType(match, replacement))
+    return false;
+
+  GlobalAlias *alias = GlobalAlias::create("", replacement);
+  match->replaceAllUsesWith(alias);
+  alias->takeName(match);
+  match->eraseFromParent();
+
+  return true;
+}
+
+bool FunctionAliasPass::isFunctionOrGlobalFunctionAlias(const GlobalValue *gv) {
+  if (gv == nullptr)
+    return false;
+
+  if (isa<Function>(gv))
+    return true;
+
+  if (const auto *ga = dyn_cast<GlobalAlias>(gv)) {
+    const auto *aliasee = dyn_cast<GlobalValue>(ga->getAliasee());
+    if (!aliasee) {
+      // check if GlobalAlias is alias bitcast
+      const auto *cexpr = dyn_cast<ConstantExpr>(ga->getAliasee());
+      if (!cexpr || !cexpr->isCast())
+        return false;
+      aliasee = dyn_cast<GlobalValue>(cexpr->getOperand(0));
+    }
+    return isFunctionOrGlobalFunctionAlias(aliasee);
+  }
+
+  return false;
+}
+
+char FunctionAliasPass::ID = 0;
+
+} // namespace klee
diff --git a/lib/Module/KModule.cpp b/lib/Module/KModule.cpp
index 2ee49f23..315942b5 100644
--- a/lib/Module/KModule.cpp
+++ b/lib/Module/KModule.cpp
@@ -287,6 +287,7 @@ void KModule::optimiseAndPrepare(
   }
   pm3.add(new IntrinsicCleanerPass(*targetData));
   pm3.add(new PhiCleanerPass());
+  pm3.add(new FunctionAliasPass());
   pm3.run(*module);
 }
 
diff --git a/lib/Module/Passes.h b/lib/Module/Passes.h
index d5f8d821..4fb0cfd7 100644
--- a/lib/Module/Passes.h
+++ b/lib/Module/Passes.h
@@ -167,6 +167,24 @@ public:
   bool checkPassed() const { return instructionOperandsConform; }
 };
 
+/// FunctionAliasPass - Enables a user of KLEE to specify aliases to functions
+/// using -function-alias=<name|pattern>:<replacement> which are injected as
+/// GlobalAliases into the module. The replaced function is removed.
+class FunctionAliasPass : public llvm::ModulePass {
+
+public:
+  static char ID;
+  FunctionAliasPass() : llvm::ModulePass(ID) {}
+  bool runOnModule(llvm::Module &M) override;
+
+private:
+  static const llvm::FunctionType *getFunctionType(const llvm::GlobalValue *gv);
+  static bool checkType(const llvm::GlobalValue *match, const llvm::GlobalValue *replacement);
+  static bool tryToReplace(llvm::GlobalValue *match, llvm::GlobalValue *replacement);
+  static bool isFunctionOrGlobalFunctionAlias(const llvm::GlobalValue *gv);
+
+};
+
 #ifdef USE_WORKAROUND_LLVM_PR39177
 /// WorkaroundLLVMPR39177Pass - Workaround for LLVM PR39177 within KLEE repo.
 /// For more information on this, please refer to the comments in
diff --git a/test/Feature/FunctionAlias.c b/test/Feature/FunctionAlias.c
new file mode 100644
index 00000000..2fcb5beb
--- /dev/null
+++ b/test/Feature/FunctionAlias.c
@@ -0,0 +1,89 @@
+// RUN: %clang %s -emit-llvm %O0opt -c -o %t.bc
+// RUN: rm -rf %t.klee-out
+// RUN: not %klee --output-dir=%t.klee-out -function-alias=:oneint %t.bc 2>&1 | FileCheck --check-prefix=CHECK-EMPTY --check-prefix=CHECK-ERROR %s
+// RUN: rm -rf %t.klee-out
+// RUN: not %klee --output-dir=%t.klee-out -function-alias=oneint: %t.bc 2>&1 | FileCheck --check-prefix=CHECK-EMPTY --check-prefix=CHECK-ERROR %s
+// RUN: rm -rf %t.klee-out
+// RUN: not %klee --output-dir=%t.klee-out -function-alias=oneint:oneint %t.bc 2>&1 | FileCheck --check-prefix=CHECK-SAME --check-prefix=CHECK-ERROR %s
+// RUN: rm -rf %t.klee-out
+// RUN: not %klee --output-dir=%t.klee-out -function-alias=oneint:oneshort %t.bc 2>&1 | FileCheck --check-prefix=CHECK-TYPE-MISMATCH --check-prefix=CHECK-ERROR %s
+// RUN: rm -rf %t.klee-out
+// RUN: not %klee --output-dir=%t.klee-out -function-alias=oneint:twoints %t.bc 2>&1 | FileCheck --check-prefix=CHECK-TYPE-MISMATCH --check-prefix=CHECK-ERROR %s
+// RUN: rm -rf %t.klee-out
+// RUN: not %klee --output-dir=%t.klee-out -function-alias=twoints:twoshorts2int %t.bc 2>&1 | FileCheck --check-prefix=CHECK-TYPE-MISMATCH --check-prefix=CHECK-ERROR %s
+// RUN: rm -rf %t.klee-out
+// RUN: not %klee --output-dir=%t.klee-out -function-alias=oneint:unknownfunction %t.bc 2>&1 | FileCheck --check-prefix=CHECK-UNKNOWN --check-prefix=CHECK-ERROR %s
+// RUN: rm -rf %t.klee-out
+// RUN: %klee --output-dir=%t.klee-out -function-alias=twoints:twointsmul %t.bc 2>&1 | FileCheck --check-prefix=CHECK-SUCCESS %s
+// RUN: rm -rf %t.klee-out
+// RUN: not %klee --output-dir=%t.klee-out -function-alias=xxx.*:somethingwithtwoints %t.bc 2>&1 | FileCheck --check-prefix=CHECK-REGEX-NO-MATCH --check-prefix=CHECK-ERROR %s
+// RUN: rm -rf %t.klee-out
+// RUN: %klee --output-dir=%t.klee-out -function-alias=twoints.*:somethingwithtwoints %t.bc 2>&1 | FileCheck --check-prefix=CHECK-REGEX-PREFIX %s
+// RUN: rm -rf %t.klee-out
+// RUN: %klee --output-dir=%t.klee-out -function-alias=.*twoints.*:twoints %t.bc 2>&1 | FileCheck --check-prefix=CHECK-REGEX-INFIX %s
+// RUN: rm -rf %t.klee-out
+// RUN: %klee --output-dir=%t.klee-out -function-alias=two.*:twoints %t.bc 2>&1 | FileCheck --check-prefix=CHECK-REGEX-TYPE-MISMATCH %s
+// RUN: rm -rf %t.klee-out
+// RUN: %klee --output-dir=%t.klee-out -function-alias=somethingwith.*:twoints -function-alias=twoints:twointsmul %t.bc 2>&1 | FileCheck --check-prefix=CHECK-MULTIPLE %s
+// RUN: rm -rf %t.klee-out
+// RUN: %klee --output-dir=%t.klee-out -output-module -function-alias=oneshort:shortminusone %t.bc 2>&1 | FileCheck --check-prefix=CHECK-BITCAST-ALIAS %s
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+// CHECK-EMPTY: KLEE: ERROR: function-alias: {{name or pattern|replacement}} cannot be empty
+
+// CHECK-SAME: KLEE: ERROR: function-alias: @oneint cannot replace itself
+
+// CHECK-TYPE-MISMATCH: KLEE: WARNING: function-alias: @{{[a-z0-9]+}} could not be replaced with @{{[a-z0-9]+}}
+
+// CHECK-SUCCESS: KLEE: function-alias: replaced @twoints with @twointsmul
+
+// CHECK-REGEX-NO-MATCH: KLEE: ERROR: function-alias: no (replacable) match for 'xxx.*' found
+
+// CHECK-REGEX-PREFIX: KLEE: function-alias: replaced @twoints (matching 'twoints.*') with @somethingwithtwoints
+// CHECK-REGEX-PREFIX: KLEE: function-alias: replaced @twointsmul (matching 'twoints.*') with @somethingwithtwoints
+
+// CHECK-REGEX-INFIX: KLEE: WARNING: function-alias: do not replace @twoints (matching '.*twoints.*') with @twoints: cannot replace itself
+// CHECK-REGEX-INFIX: KLEE: function-alias: replaced @twointsmul (matching '.*twoints.*') with @twoints
+// CHECK-REGEX-INFIX: KLEE: function-alias: replaced @somethingwithtwoints (matching '.*twoints.*') with @twoints
+
+// CHECK-REGEX-TYPE-MISMATCH: KLEE: WARNING: function-alias: @twoshorts2int could not be replaced with @twoints: parameter types differ
+// CHECK-REGEX-TYPE-MISMATCH: KLEE: function-alias: replaced @twointsmul (matching 'two.*') with @twoints
+
+// CHECK-MULTIPLE: KLEE: function-alias: replaced @somethingwithtwoints (matching 'somethingwith.*') with @twoints
+// CHECK-MULTIPLE: KLEE: function-alias: replaced @twoints with @twointsmul
+
+// CHECK-BITCAST-ALIAS: function-alias: replaced @oneshort with @shortminusone
+
+int __attribute__ ((noinline)) oneint(int a) { return a; }
+short __attribute__ ((noinline)) oneshort(short a) { return a + 1; }
+int __attribute__ ((noinline)) minusone(int a) { return a - 1; }
+int __attribute__ ((noinline)) twoints(int a, int b) { return a + b; }
+int __attribute__ ((noinline)) twoshorts2int(short a, short b) { return a + b + 2; }
+int __attribute__ ((noinline)) twointsmul(int a, int b) { return a * b + 5; }
+int __attribute__ ((noinline)) somethingwithtwoints(int a, int b) { return 2 * a + 3 * b; }
+
+extern short shortminusone(short) __attribute__((alias("minusone")));
+
+int main() {
+  short a = 2;
+  short b = 3;
+  int result = 0;
+  result += shortminusone(a);
+  result += oneint(a);
+  result += oneshort(a);
+  result += twoints(a, b);
+  result += twoshorts2int(a, b);
+  result += twointsmul(a, b);
+  result += somethingwithtwoints(a, b);
+  // CHECK-ERROR-NOT: result =
+  // CHECK-SUCCESS: result = 48
+  // CHECK-REGEX-PREFIX: result = 52
+  // CHECK-REGEX-INFIX: result = 28
+  // CHECK-REGEX-TYPE-MISMATCH: result = 36
+  // CHECK-MULTIPLE: result = 46
+  // CHECK-BITCAST-ALIAS: 40
+  printf("result = %d\n", result);
+}
diff --git a/test/Feature/FunctionAliasExit.c b/test/Feature/FunctionAliasExit.c
new file mode 100644
index 00000000..b30838d0
--- /dev/null
+++ b/test/Feature/FunctionAliasExit.c
@@ -0,0 +1,31 @@
+// RUN: %clang %s -emit-llvm %O0opt -c -o %t.bc
+// RUN: rm -rf %t.klee-out
+// RUN: %klee --output-dir=%t.klee-out -function-alias=exit:end %t.bc 2>&1 | FileCheck %s
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+// CHECK: KLEE: function-alias: replaced @exit with @end
+
+void start(int x) {
+  // CHECK: START
+  printf("START\n");
+  if (x == 53)
+    // CHECK: END: status = 1
+    exit(1);
+}
+
+void __attribute__ ((noinline)) end(int status) {
+  printf("END: status = %d\n", status);
+  klee_silent_exit(status);
+}
+
+int main() {
+  int x;
+  klee_make_symbolic(&x, sizeof(x), "x");
+
+  start(x);
+  // CHECK: END: status = 0
+  end(0);
+}
diff --git a/test/Feature/FunctionAliasVarArg.c b/test/Feature/FunctionAliasVarArg.c
new file mode 100644
index 00000000..17893772
--- /dev/null
+++ b/test/Feature/FunctionAliasVarArg.c
@@ -0,0 +1,58 @@
+// RUN: %clang %s -emit-llvm %O0opt -c -o %t.bc
+// RUN: rm -rf %t.klee-out
+// RUN: %klee --output-dir=%t.klee-out -function-alias=printf:highlight_prefix_printf %t.bc 2>&1 | FileCheck --check-prefix=CHECK-HIGHLIGHT %s
+// RUN: rm -rf %t.klee-out
+// RUN: not %klee --output-dir=%t.klee-out -function-alias=printf:printf_format_only %t.bc 2>&1 | FileCheck --check-prefix=CHECK-VA-FAIL %s
+// RUN: rm -rf %t.klee-out
+// RUN: %klee --output-dir=%t.klee-out -function-alias=printf:printf_format_only_with_varargs %t.bc 2>&1 | FileCheck --check-prefix=CHECK-VA-SUCCESS %s
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+// CHECK-HIGHLIGHT: KLEE: function-alias: replaced @printf with @highlight_prefix_printf
+int highlight_prefix_printf(const char *format, ...) {
+  va_list args;
+  int result;
+  const char *bold_start = "*+*";
+  const char *bold_end = "*+*";
+
+  va_start(args, format);
+  const char *prefix = va_arg(args, const char *);
+
+  const char *prefixless_format = strstr(format, "%s") + 2;
+  size_t new_length = strlen(bold_start) + strlen(prefix) + strlen(bold_end) + strlen(prefixless_format) + 1;
+  char *new_format = (char *)malloc(new_length);
+  memset(new_format, 0, new_length);
+  strcat(new_format, bold_start);
+  strcat(new_format, prefix);
+  strcat(new_format, bold_end);
+  strcat(new_format, prefixless_format);
+  result = vfprintf(stdout, new_format, args);
+  va_end(args);
+
+  free(new_format);
+  return result;
+}
+
+// CHECK-VA-FAIL: KLEE: WARNING: function-alias: @printf could not be replaced with @printf_format_only: one has varargs while the other does not
+int printf_format_only(const char *format) {
+  int result;
+  result = puts(format);
+  return result;
+}
+
+// CHECK-VA-SUCCESS: KLEE: function-alias: replaced @printf with @printf_format_only_with_varargs
+int printf_format_only_with_varargs(const char *format, ...) {
+  int result;
+  result = puts(format);
+  return result;
+}
+
+int main() {
+  int i = 42;
+  // CHECK: KLEE: some warning about 42
+  // CHECK-HIGHLIGHT: *+*KLEE*+*
+  // CHECK-VA-SUCCESS: %s: some warning about %d
+  printf("%s: some warning about %d\n", "KLEE", i);
+}