text: /*
   * Copyright (c) 2020 Trail of Bits, Inc.
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *     http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  #include <gflags/gflags.h>
  #include <glog/logging.h>
  
  #include <sstream>
  #include <system_error>
  #include <unordered_map>
  #include <utility>
  #include <vector>
  
  #ifndef WIN32
  #  include <sys/stat.h>
  #  include <unistd.h>
  #endif
  
  #include <llvm/ADT/SmallVector.h>
  #include <llvm/ADT/StringExtras.h>
  #include <llvm/IR/BasicBlock.h>
  #include <llvm/IR/Constants.h>
  #include <llvm/IR/Function.h>
  #include <llvm/IR/IRBuilder.h>
  #include <llvm/IR/Instructions.h>
  #include <llvm/IR/IntrinsicInst.h>
  #include <llvm/IR/LLVMContext.h>
  #include <llvm/IR/Metadata.h>
  #include <llvm/IR/Module.h>
  #include <llvm/Support/FileSystem.h>
  #include <llvm/Support/SourceMgr.h>
  #include <llvm/Support/raw_ostream.h>
  
  #include "remill/Arch/Arch.h"
  #include "remill/Arch/Name.h"
  #include "remill/BC/ABI.h"
  #include "remill/BC/Annotate.h"
  #include "remill/BC/Compat/BitcodeReaderWriter.h"
  #include "remill/BC/Compat/CallSite.h"
  #include "remill/BC/Compat/DebugInfo.h"
  #include "remill/BC/Compat/GlobalValue.h"
  #include "remill/BC/Compat/IRReader.h"
  #include "remill/BC/Compat/ToolOutputFile.h"
  #include "remill/BC/Compat/VectorType.h"
  #include "remill/BC/Compat/Verifier.h"
  #include "remill/BC/IntrinsicTable.h"
  #include "remill/BC/Util.h"
  #include "remill/BC/Version.h"
  #include "remill/OS/FileSystem.h"
  
  DECLARE_string(arch);
  
  DEFINE_string(
      semantics_search_paths, "",
      "Colon-separated list of search paths to use when searching for semantics files.");
  
  namespace {
  #ifdef WIN32
  extern "C" std::uint32_t GetProcessId(std::uint32_t handle);
  #endif
  
  // We are avoiding the `getpid` name here to make sure we don't
  // conflict with the (deprecated) getpid function from the Windows
  // ucrt headers
  std::uint32_t nativeGetProcessID(void) {
  #ifdef WIN32
    return GetProcessId(0);
  #else
    return getpid();
  #endif
  }
  }  // namespace
  
  namespace remill {
  
  // Initialize the attributes for a lifted function.
  void InitFunctionAttributes(llvm::Function *function) {
  
    // Make sure functions are treated as if they return. LLVM doesn't like
    // mixing must-tail-calls with no-return.
    function->removeFnAttr(llvm::Attribute::NoReturn);
  
    // Don't use any exception stuff.
    function->removeFnAttr(llvm::Attribute::UWTable);
    function->removeFnAttr(llvm::Attribute::NoInline);
    function->addFnAttr(llvm::Attribute::NoUnwind);
    function->addFnAttr(llvm::Attribute::InlineHint);
  }
  
  // Create a call from one lifted function to another.
  llvm::CallInst *AddCall(llvm::BasicBlock *source_block,
                          llvm::Value *dest_func) {
    llvm::IRBuilder<> ir(source_block);
    auto args = LiftedFunctionArgs(source_block);
  #if LLVM_VERSION_NUMBER < LLVM_VERSION(11, 0)
    return ir.CreateCall(dest_func, args);
  #else
    if (auto func = llvm::dyn_cast<llvm::Function>(dest_func); func) {
      return ir.CreateCall(func, args);
  
    } else {
      llvm::Type *arg_types[kNumBlockArgs];
      arg_types[kStatePointerArgNum] = args[kStatePointerArgNum]->getType();
      arg_types[kMemoryPointerArgNum] = args[kMemoryPointerArgNum]->getType();
      arg_types[kPCArgNum] = args[kPCArgNum]->getType();
      auto func_type = llvm::FunctionType::get(
          arg_types[kMemoryPointerArgNum], arg_types, false);
      llvm::FunctionCallee callee(func_type, dest_func);
      return ir.CreateCall(callee, args);
    }
  #endif
  }
  
  // Create a tail-call from one lifted function to another.
  llvm::CallInst *AddTerminatingTailCall(llvm::Function *source_func,
                                         llvm::Value *dest_func) {
    if (source_func->isDeclaration()) {
      llvm::IRBuilder<> ir(
          llvm::BasicBlock::Create(source_func->getContext(), "", source_func));
    }
    return AddTerminatingTailCall(&(source_func->back()), dest_func);
  }
  
  llvm::CallInst *AddTerminatingTailCall(llvm::BasicBlock *source_block,
                                         llvm::Value *dest_func) {
    CHECK(nullptr != dest_func) << "Target function/block does not exist!";
  
    LOG_IF(ERROR, source_block->getTerminator())
        << "Block already has a terminator; not adding fall-through call to: "
        << (dest_func ? dest_func->getName().str() : "<unreachable>");
  
    llvm::IRBuilder<> ir(source_block);
  
    // get the `NEXT_PC` and set it to `PC`
    auto next_pc = LoadNextProgramCounter(source_block);
    auto pc_ref = LoadProgramCounterRef(source_block);
    (void) new llvm::StoreInst(next_pc, pc_ref, source_block);
  
    auto call_target_instr = AddCall(source_block, dest_func);
    call_target_instr->setTailCall(true);
  
    ir.CreateRet(call_target_instr);
    return call_target_instr;
  }
  
  // Find a local variable defined in the entry block of the function. We use
  // this to find register variables.
  llvm::Value *FindVarInFunction(llvm::BasicBlock *block, std::string_view name,
                                 bool allow_failure) {
    return FindVarInFunction(block->getParent(), name, allow_failure);
  }
  
  // Find a local variable defined in the entry block of the function. We use
  // this to find register variables.
  llvm::Value *FindVarInFunction(llvm::Function *function,
                                 std::string_view name_, bool allow_failure) {
    llvm::StringRef name(name_.data(), name_.size());
    if (!function->empty()) {
      for (auto &instr : function->getEntryBlock()) {
        if (instr.getName() == name) {
          return &instr;
        }
      }
    }
  
    for (auto &arg : function->args()) {
      if (arg.getName() == name) {
        return &arg;
      }
    }
  
    auto module = function->getParent();
    if (auto var = module->getGlobalVariable(name)) {
      return var;
    }
  
    CHECK(allow_failure) << "Could not find variable " << name_ << " in function "
                         << function->getName().str();
    return nullptr;
  }
  
  // Find the machine state pointer.
  llvm::Value *LoadStatePointer(llvm::Function *function) {
    CHECK(kNumBlockArgs == function->arg_size())
        << "Invalid block-like function. Expected three arguments: state "
        << "pointer, program counter, and memory pointer in function "
        << function->getName().str();
  
    static_assert(0 == kStatePointerArgNum,
                  "Expected state pointer to be the first operand.");
  
    return NthArgument(function, kStatePointerArgNum);
  }
  
  // Return the memory pointer argument.
  llvm::Value *LoadMemoryPointerArg(llvm::Function *function) {
    CHECK(kNumBlockArgs == function->arg_size())
        << "Invalid block-like function. Expected three arguments: state "
        << "pointer, program counter, and memory pointer in function "
        << function->getName().str();
  
    static_assert(2 == kMemoryPointerArgNum,
                  "Expected state pointer to be the first operand.");
  
    return NthArgument(function, kMemoryPointerArgNum);
  }
  
  // Return the program counter argument.
  llvm::Value *LoadProgramCounterArg(llvm::Function *function) {
    CHECK(kNumBlockArgs == function->arg_size())
        << "Invalid block-like function. Expected three arguments: state "
        << "pointer, program counter, and memory pointer in function "
        << function->getName().str();
  
    static_assert(1 == kPCArgNum,
                  "Expected state pointer to be the first operand.");
  
    return NthArgument(function, kPCArgNum);
  }
  
  llvm::Value *LoadStatePointer(llvm::BasicBlock *block) {
    return LoadStatePointer(block->getParent());
  }
  
  // Return the current program counter.
  llvm::Value *LoadProgramCounter(llvm::BasicBlock *block) {
    llvm::IRBuilder<> ir(block);
    return ir.CreateLoad(LoadProgramCounterRef(block));
  }
  
  // Return a reference to the current program counter.
  llvm::Value *LoadProgramCounterRef(llvm::BasicBlock *block) {
    return FindVarInFunction(block->getParent(), kPCVariableName);
  }
  
  // Return a reference to the next program counter.
  llvm::Value *LoadNextProgramCounterRef(llvm::BasicBlock *block) {
    return FindVarInFunction(block->getParent(), kNextPCVariableName);
  }
  
  // Return the next program counter.
  llvm::Value *LoadNextProgramCounter(llvm::BasicBlock *block) {
    llvm::IRBuilder<> ir(block);
    return ir.CreateLoad(LoadNextProgramCounterRef(block));
  }
  
  // Return a reference to the return program counter.
  llvm::Value *LoadReturnProgramCounterRef(llvm::BasicBlock *block) {
    return FindVarInFunction(block->getParent(), kReturnPCVariableName);
  }
  
  // Update the program counter in the state struct with a new value.
  void StoreProgramCounter(llvm::BasicBlock *block, llvm::Value *pc) {
    (void) new llvm::StoreInst(pc, LoadProgramCounterRef(block), block);
  }
  
  // Update the next program counter in the state struct with a new value.
  void StoreNextProgramCounter(llvm::BasicBlock *block, llvm::Value *pc) {
    (void) new llvm::StoreInst(pc, LoadNextProgramCounterRef(block), block);
  }
  
  // Update the program counter in the state struct with a hard-coded value.
  void StoreProgramCounter(llvm::BasicBlock *block, uint64_t pc) {
    auto pc_ptr = LoadProgramCounterRef(block);
    auto type = llvm::dyn_cast<llvm::PointerType>(pc_ptr->getType());
    (void) new llvm::StoreInst(llvm::ConstantInt::get(type->getElementType(), pc),
                               pc_ptr, block);
  }
  
  // Return the current memory pointer.
  llvm::Value *LoadMemoryPointer(llvm::BasicBlock *block) {
    llvm::IRBuilder<> ir(block);
    return ir.CreateLoad(LoadMemoryPointerRef(block));
  }
  
  // Return an `llvm::Value *` that is an `i1` (bool type) representing whether
  // or not a conditional branch is taken.
  llvm::Value *LoadBranchTaken(llvm::BasicBlock *block) {
    llvm::IRBuilder<> ir(block);
    auto cond = ir.CreateLoad(
        FindVarInFunction(block->getParent(), kBranchTakenVariableName));
    auto true_val = llvm::ConstantInt::get(cond->getType(), 1);
    return ir.CreateICmpEQ(cond, true_val);
  }
  
  // Return a reference to the branch taken
  llvm::Value *LoadBranchTakenRef(llvm::BasicBlock *block) {
    return FindVarInFunction(block->getParent(), kBranchTakenVariableName);
  }
  
  // Return a reference to the memory pointer.
  llvm::Value *LoadMemoryPointerRef(llvm::BasicBlock *block) {
    return FindVarInFunction(block->getParent(), kMemoryVariableName);
  }
  
  // Find a function with name `name` in the module `M`.
  llvm::Function *FindFunction(llvm::Module *module, std::string_view name_) {
    llvm::StringRef name(name_.data(), name_.size());
    return module->getFunction(name);
  }
  
  // Find a global variable with name `name` in the module `M`.
  llvm::GlobalVariable *FindGlobaVariable(llvm::Module *module,
                                          std::string_view name_) {
    llvm::StringRef name(name_.data(), name_.size());
    return module->getGlobalVariable(name, true);
  }
  
  // Loads the semantics for the `arch`-specific machine, i.e. the machine of the
  // code that we want to lift.
  std::unique_ptr<llvm::Module> LoadArchSemantics(const Arch *arch) {
    auto arch_name = GetArchName(arch->arch_name);
    auto path = FindSemanticsBitcodeFile(arch_name);
    LOG(INFO) << "Loading " << arch_name << " semantics from file " << path;
    auto module = LoadModuleFromFile(arch->context, path);
    arch->PrepareModule(module);
    arch->InitFromSemanticsModule(module.get());
    for (auto &func : *module) {
      Annotate<remill::Semantics>(&func);
    }
    return module;
  }
  
  // Try to verify a module.
  bool VerifyModule(llvm::Module *module) {
    std::string error;
    llvm::raw_string_ostream error_stream(error);
    if (llvm::verifyModule(*module, &error_stream)) {
      error_stream.flush();
      LOG(ERROR) << "Error verifying module read from file: " << error;
      return false;
    } else {
      return true;
    }
  }
  
  // Reads an LLVM module from a file.
  std::unique_ptr<llvm::Module> LoadModuleFromFile(llvm::LLVMContext *context,
                                                   std::string_view file_name_,
                                                   bool allow_failure) {
    llvm::SMDiagnostic err;
    llvm::StringRef file_name(file_name_.data(), file_name_.size());
    auto module = llvm::parseIRFile(file_name, err, *context);
  
    if (!module) {
      LOG_IF(FATAL, !allow_failure)
          << "Unable to parse module file " << file_name_
          << ": " << err.getMessage().str();
      return {};
    }
  
    auto ec = module->materializeAll();  // Just in case.
    if (ec) {
      LOG_IF(FATAL, !allow_failure)
          << "Unable to materialize everything from " << file_name_;
      return {};
    }
  
    if (!VerifyModule(module.get())) {
      LOG_IF(FATAL, !allow_failure)
          << "Error verifying module read from file " << file_name_;
      return {};
    }
  
    return module;
  }
  
  // Store an LLVM module into a file.
  bool StoreModuleToFile(llvm::Module *module, std::string_view file_name,
                         bool allow_failure) {
    DLOG(INFO) << "Saving bitcode to file " << file_name;
  
    std::stringstream ss;
    ss << file_name << ".tmp." << nativeGetProcessID();
    auto tmp_name = ss.str();
  
    std::string error;
    llvm::raw_string_ostream error_stream(error);
  
    if (llvm::verifyModule(*module, &error_stream)) {
      error_stream.flush();
      LOG_IF(FATAL, !allow_failure)
          << "Error writing module to file " << file_name << ": " << error;
      return false;
    }
  
  #if LLVM_VERSION_NUMBER > LLVM_VERSION(3, 5)
    std::error_code ec;
  #  if LLVM_VERSION_NUMBER < LLVM_VERSION(7, 0)
    llvm::ToolOutputFile bc(tmp_name.c_str(), ec, llvm::sys::fs::F_RW);
  #  else
    llvm::ToolOutputFile bc(tmp_name.c_str(), ec, llvm::sys::fs::OF_None);
  #  endif
    CHECK(!ec) << "Unable to open output bitcode file for writing: " << tmp_name;
  #else
    llvm::tool_output_file bc(tmp_name.c_str(), error, llvm::sys::fs::F_RW);
    CHECK(error.empty() && !bc.os().has_error())
        << "Unable to open output bitcode file for writing: " << tmp_name << ": "
        << error;
  #endif
  
  #if LLVM_VERSION_NUMBER < LLVM_VERSION(7, 0)
    llvm::WriteBitcodeToFile(module, bc.os());
  #else
    llvm::WriteBitcodeToFile(*module, bc.os());
  #endif
    bc.keep();
    if (!bc.os().has_error()) {
      std::string file_name_(file_name.data(), file_name.size());
      MoveFile(tmp_name, file_name_);
      return true;
  
    } else {
      RemoveFile(tmp_name);
      LOG_IF(FATAL, !allow_failure)
          << "Error writing bitcode to file: " << file_name << ".";
      return false;
    }
  }
  
  // Store a module, serialized to LLVM IR, into a file.
  bool StoreModuleIRToFile(llvm::Module *module, std::string_view file_name_,
                           bool allow_failure) {
    std::string file_name(file_name_.data(), file_name_.size());
  #if LLVM_VERSION_NUMBER > LLVM_VERSION(3, 5)
    std::error_code ec;
    llvm::raw_fd_ostream dest(file_name.c_str(), ec, llvm::sys::fs::F_Text);
    auto good = !ec;
    auto error = ec.message();
  #else
    std::string error;
    llvm::raw_fd_ostream dest(file_name.c_str(), error, llvm::sys::fs::F_Text);
    auto good = error.empty();
  #endif
    if (!good) {
      LOG_IF(FATAL, allow_failure)
          << "Could not save LLVM IR to " << file_name << ": " << error;
      return false;
    }
    module->print(dest, nullptr);
    return true;
  }
  
  namespace {
  
  #ifndef REMILL_BUILD_SEMANTICS_DIR_X86
  #  error \
        "Macro `REMILL_BUILD_SEMANTICS_DIR_X86` must be defined to support X86 and AMD64 architectures."
  #  define REMILL_BUILD_SEMANTICS_DIR_X86
  #endif  // REMILL_BUILD_SEMANTICS_DIR_X86
  
  #ifndef REMILL_BUILD_SEMANTICS_DIR_AARCH64
  #  error \
        "Macro `REMILL_BUILD_SEMANTICS_DIR_AARCH64` must be defined to support AArch64 architecture."
  #  define REMILL_BUILD_SEMANTICS_DIR_AARCH64
  #endif  // REMILL_BUILD_SEMANTICS_DIR_AARCH64
  
  #ifndef REMILL_BUILD_SEMANTICS_DIR_SPARC32
  #error "Macro `REMILL_BUILD_SEMANTICS_DIR_SPARC32` must be defined to support the SPARC32 architectures."
  #define REMILL_BUILD_SEMANTICS_DIR_SPARC32
  #endif  // REMILL_BUILD_SEMANTICS_DIR_SPARC32
  
  #ifndef REMILL_BUILD_SEMANTICS_DIR_SPARC64
  #error "Macro `REMILL_BUILD_SEMANTICS_DIR_SPARC64` must be defined to support the SPARC64 architectures."
  #define REMILL_BUILD_SEMANTICS_DIR_SPARC64
  #endif  // REMILL_BUILD_SEMANTICS_DIR_SPARC64
  
  #ifndef REMILL_INSTALL_SEMANTICS_DIR
  #  error "Macro `REMILL_INSTALL_SEMANTICS_DIR` must be defined."
  #  define REMILL_INSTALL_SEMANTICS_DIR
  #endif  // REMILL_INSTALL_SEMANTICS_DIR
  
  #define _S(x) #x
  #define S(x) _S(x)
  #define MAJOR_MINOR S(LLVM_VERSION_MAJOR) "." S(LLVM_VERSION_MINOR)
  
  static const char *gSemanticsSearchPaths[] = {
    // Derived from the build.
    REMILL_BUILD_SEMANTICS_DIR_X86 "\0",
    REMILL_BUILD_SEMANTICS_DIR_AARCH64 "\0",
    REMILL_BUILD_SEMANTICS_DIR_SPARC32 "\0",
    REMILL_BUILD_SEMANTICS_DIR_SPARC64 "\0",
    REMILL_INSTALL_SEMANTICS_DIR "\0",
    "/usr/local/share/remill/" MAJOR_MINOR "/semantics",
    "/usr/share/remill/" MAJOR_MINOR "/semantics",
    "/share/remill/" MAJOR_MINOR "/semantics",
  };
  
  }  // namespace
  
  // Find the path to the semantics bitcode file associated with `FLAGS_arch`.
  std::string FindTargetSemanticsBitcodeFile(void) {
    return FindSemanticsBitcodeFile(FLAGS_arch);
  }
  
  // Find the path to the semantics bitcode file associated with `REMILL_ARCH`,
  // the architecture on which remill is compiled.
  std::string FindHostSemanticsBitcodeFile(void) {
    return FindSemanticsBitcodeFile(REMILL_ARCH);
  }
  
  // Find the path to the semantics bitcode file.
  std::string FindSemanticsBitcodeFile(std::string_view arch) {
    if (!FLAGS_semantics_search_paths.empty()) {
      std::stringstream pp;
      pp << FLAGS_semantics_search_paths;
      for (std::string sem_dir; std::getline(pp, sem_dir, ':');) {
        std::stringstream ss;
        ss << sem_dir << "/" << arch << ".bc";
        if (auto sem_path = ss.str(); FileExists(sem_path)) {
          return sem_path;
        }
      }
    }
  
    for (auto sem_dir : gSemanticsSearchPaths) {
      std::stringstream ss;
      ss << sem_dir << "/" << arch << ".bc";
      if (auto sem_path = ss.str(); FileExists(sem_path)) {
        return sem_path;
      }
    }
  
    LOG(FATAL) << "Cannot find path to " << arch << " semantics bitcode file.";
    return "";
  }
  
  namespace {
  
  // Convert an LLVM thing (e.g. `llvm::Value` or `llvm::Type`) into
  // a `std::string`.
  template <typename T>
  inline static std::string DoLLVMThingToString(T *thing) {
    if (thing) {
      std::string str;
      llvm::raw_string_ostream str_stream(str);
      thing->print(str_stream);
      return str;
    } else {
      return "(null)";
    }
  }
  
  }  // namespace
  
  std::string LLVMThingToString(llvm::Value *thing) {
    return DoLLVMThingToString(thing);
  }
  
  std::string LLVMThingToString(llvm::Type *thing) {
    return DoLLVMThingToString(thing);
  }
  
  llvm::Argument *NthArgument(llvm::Function *func, size_t index) {
    auto it = func->arg_begin();
    if (index >= static_cast<size_t>(std::distance(it, func->arg_end()))) {
      return nullptr;
    }
    std::advance(it, index);
    return &*it;
  }
  
  // Returns a pointer to the `__remill_basic_block` function.
  llvm::Function *BasicBlockFunction(llvm::Module *module) {
    auto bb = module->getFunction("__remill_basic_block");
    CHECK(nullptr != bb);
    return bb;
  }
  
  // Return the type of a lifted function.
  llvm::FunctionType *LiftedFunctionType(llvm::Module *module) {
    return BasicBlockFunction(module)->getFunctionType();
  }
  
  // Return a vector of arguments to pass to a lifted function, where the
  // arguments are derived from `block`.
  std::array<llvm::Value *, kNumBlockArgs>
  LiftedFunctionArgs(llvm::BasicBlock *block) {
    auto func = block->getParent();
  
    // Set up arguments according to our ABI.
    std::array<llvm::Value *, kNumBlockArgs> args;
  
    if (FindVarInFunction(func, kPCVariableName, true)) {
      args[kMemoryPointerArgNum] = LoadMemoryPointer(block);
      args[kStatePointerArgNum] = LoadStatePointer(block);
      args[kPCArgNum] = LoadProgramCounter(block);
    } else {
      args[kMemoryPointerArgNum] = NthArgument(func, kMemoryPointerArgNum);
      args[kStatePointerArgNum] = NthArgument(func, kStatePointerArgNum);
      args[kPCArgNum] = NthArgument(func, kPCArgNum);
    }
  
    return args;
  }
  
  // Apply a callback function to every semantics bitcode function.
  void ForEachISel(llvm::Module *module, ISelCallback callback) {
    for (auto &global : module->globals()) {
      const auto &name = global.getName();
      if (name.startswith("ISEL_") || name.startswith("COND_")) {
        llvm::Function *sem = nullptr;
        if (global.hasInitializer()) {
          sem = llvm::dyn_cast<llvm::Function>(
              global.getInitializer()->stripPointerCasts());
        }
        callback(&global, sem);
      }
    }
  }
  
  // Declare a lifted function of the correct type.
  llvm::Function *DeclareLiftedFunction(llvm::Module *module,
                                        std::string_view name_) {
    llvm::StringRef name(name_.data(), name_.size());
    auto func = module->getFunction(name);
    if (!func) {
      auto bb = BasicBlockFunction(module);
      auto func_type = bb->getFunctionType();
      llvm::StringRef name_str(name.data(), name.size());
      func = llvm::Function::Create(func_type, llvm::GlobalValue::InternalLinkage,
                                    name_str, module);
      InitFunctionAttributes(func);
    }
  
    return func;
  }
  
  #pragma GCC diagnostic push
  #pragma GCC diagnostic ignored "-Wdeprecated-declarations"
  
  // Returns the type of a state pointer.
  llvm::PointerType *StatePointerType(llvm::Module *module) {
    return llvm::dyn_cast<llvm::PointerType>(
        LiftedFunctionType(module)->getParamType(kStatePointerArgNum));
  }
  
  // Returns the type of a state pointer.
  llvm::PointerType *MemoryPointerType(llvm::Module *module) {
    return llvm::dyn_cast<llvm::PointerType>(
        LiftedFunctionType(module)->getParamType(kMemoryPointerArgNum));
  }
  
  // Returns the type of an address (addr_t in the State.h).
  llvm::IntegerType *AddressType(llvm::Module *module) {
    return llvm::dyn_cast<llvm::IntegerType>(
        LiftedFunctionType(module)->getParamType(kPCArgNum));
  }
  
  #pragma GCC diagnostic pop
  
  // Clone function `source_func` into `dest_func`. This will strip out debug
  // info during the clone.
  void CloneFunctionInto(llvm::Function *source_func, llvm::Function *dest_func) {
    auto new_args = dest_func->arg_begin();
    ValueMap value_map;
    for (llvm::Argument &old_arg : source_func->args()) {
      new_args->setName(old_arg.getName());
      value_map[&old_arg] = &*new_args;
      ++new_args;
    }
  
    CloneFunctionInto(source_func, dest_func, value_map);
  }
  
  // Make `func` a clone of the `__remill_basic_block` function.
  void CloneBlockFunctionInto(llvm::Function *func) {
    auto bb_func = BasicBlockFunction(func->getParent());
    CHECK(remill::FindVarInFunction(bb_func, kMemoryVariableName) != nullptr);
  
    CloneFunctionInto(bb_func, func);
  
    // Remove the `return` in `__remill_basic_block`.
    auto &entry = func->front();
    auto term = entry.getTerminator();
    CHECK(llvm::isa<llvm::ReturnInst>(term));
  
    term->eraseFromParent();
    func->removeFnAttr(llvm::Attribute::OptimizeNone);
  
    CHECK(remill::FindVarInFunction(func, kMemoryVariableName) != nullptr);
  }
  
  // Returns a list of callers of a specific function.
  std::vector<llvm::CallInst *> CallersOf(llvm::Function *func) {
    if (!func) {
      return {};
    }
  
    std::vector<llvm::CallInst *> callers;
    for (auto user : func->users()) {
      if (auto cs = compat::llvm::CallSite(user); cs.isCall()) {
        if (cs.getCalledFunction() == func) {
          callers.push_back(llvm::cast<llvm::CallInst>(user));
        }
      }
    }
    return callers;
  }
  
  // Returns the name of a module.
  std::string ModuleName(llvm::Module *module) {
  #if LLVM_VERSION_NUMBER < LLVM_VERSION(3, 6)
    return module->getModuleIdentifier();
  #else
    return module->getName().str();
  #endif
  }
  
  std::string ModuleName(const std::unique_ptr<llvm::Module> &module) {
    return ModuleName(module.get());
  }
  
  namespace {
  
  #if 0
  static llvm::Constant *CloneConstant(llvm::Constant *val);
  
  static std::vector<llvm::Constant *> CloneContents(
      llvm::ConstantAggregate *agg) {
    auto num_elems = agg->getNumOperands();
    std::vector<llvm::Constant *> clones(num_elems);
    for (auto i = 0U; i < num_elems; ++i) {
      clones[i] = CloneConstant(agg->getAggregateElement(i));
    }
    return clones;
  }
  
  static llvm::Constant *CloneConstant(llvm::Constant *val) {
    if (llvm::isa<llvm::ConstantData>(val) ||
        llvm::isa<llvm::ConstantAggregateZero>(val)) {
      return val;
    }
  
    std::vector<llvm::Constant *> elements;
    if (auto agg = llvm::dyn_cast<llvm::ConstantAggregate>(val)) {
      CloneContents(agg);
    }
  
    if (auto arr = llvm::dyn_cast<llvm::ConstantArray>(val)) {
      return llvm::ConstantArray::get(arr->getType(), elements);
  
    } else if (auto vec = llvm::dyn_cast<llvm::ConstantVector>(val)) {
      return llvm::ConstantVector::get(elements);
  
    } else if (auto obj = llvm::dyn_cast<llvm::ConstantStruct>(val)) {
      return llvm::ConstantStruct::get(obj->getType(), elements);
  
    } else {
      LOG(FATAL)
          << "Cannot clone " << remill::LLVMThingToString(val);
      return val;
    }
  }
  
  #endif
  
  static llvm::Function *DeclareFunctionInModule(llvm::Function *func,
                                                 llvm::Module *dest_module) {
    auto dest_func = dest_module->getFunction(func->getName());
    if (dest_func) {
      return dest_func;
    }
  
    LOG_IF(FATAL, func->hasLocalLinkage())
        << "Cannot declare internal function " << func->getName().str()
        << " as external in another module";
  
    dest_func =
        llvm::Function::Create(func->getFunctionType(), func->getLinkage(),
                               func->getName(), dest_module);
  
    dest_func->copyAttributesFrom(func);
    dest_func->setVisibility(func->getVisibility());
  
    return dest_func;
  }
  
  static llvm::GlobalVariable *DeclareVarInModule(llvm::GlobalVariable *var,
                                                  llvm::Module *dest_module);
  
  static llvm::GlobalAlias *DeclareAliasInModule(llvm::GlobalAlias *var,
                                                 llvm::Module *dest_module);
  
  template <typename T>
  static void ClearMetaData(T *value) {
    llvm::SmallVector<std::pair<unsigned, llvm::MDNode *>, 4> mds;
    value->getAllMetadata(mds);
    for (auto md_info : mds) {
      value->setMetadata(md_info.first, nullptr);
    }
  }
  
  static llvm::Constant *MoveConstantIntoModule(llvm::Constant *c,
                                                llvm::Module *dest_module) {
  
    auto &dest_context = dest_module->getContext();
    auto type = c->getType();
    auto in_same_context = true;
    if (&(c->getContext()) != &dest_context) {
      in_same_context = false;
      type = ::remill::RecontextualizeType(type, dest_context);
    } else {
  #if LLVM_VERSION_NUMBER > LLVM_VERSION(3, 8)
      if (!llvm::isa<llvm::Function>(c) &&
          !llvm::isa<llvm::GlobalVariable>(c) &&
          !llvm::isa<llvm::GlobalAlias>(c) &&
          !c->needsRelocation()) {
        LOG(ERROR) << "Not moving: " << LLVMThingToString(c);
        return c;
      }
  #endif
    }
  
    if (auto gv = llvm::dyn_cast<llvm::GlobalVariable>(c); gv) {
      return DeclareVarInModule(gv, dest_module);
  
    } else if (auto ga = llvm::dyn_cast<llvm::GlobalAlias>(c); ga) {
      return DeclareAliasInModule(ga, dest_module);
  
    } else if (auto func = llvm::dyn_cast<llvm::Function>(c); func) {
      return DeclareFunctionInModule(func, dest_module);
  
    } else if (auto d = llvm::dyn_cast<llvm::ConstantData>(c)) {
      if (auto ci = llvm::dyn_cast<llvm::ConstantInt>(d); ci) {
        if (in_same_context) {
          return ci;
        } else {
          return llvm::ConstantInt::get(type, ci->getValue());
        }
      } else if (auto cf = llvm::dyn_cast<llvm::ConstantFP>(d); cf) {
        if (in_same_context) {
          return cf;
        } else {
          return llvm::ConstantFP::get(type, cf->getValueAPF().convertToDouble());
        }
      } else if (auto u = llvm::dyn_cast<llvm::UndefValue>(d); u) {
        if (in_same_context) {
          return u;
        } else {
          return llvm::UndefValue::get(type);
        }
      } else if (auto p = llvm::dyn_cast<llvm::ConstantPointerNull>(d); p) {
        if (in_same_context) {
          return p;
        } else {
          return llvm::ConstantPointerNull::get(
              llvm::cast<llvm::PointerType>(type));
        }
      } else if (auto z = llvm::dyn_cast<llvm::ConstantAggregateZero>(d); z) {
        if (in_same_context) {
          return z;
        } else {
          return llvm::ConstantAggregateZero::get(type);
        }
      } else if (auto a = llvm::dyn_cast<llvm::ConstantDataArray>(d); a) {
        if (in_same_context) {
          return a;
        } else {
          const auto raw_data = a->getRawDataValues();
          const auto el_type = a->getElementType();
          if (el_type->isIntegerTy()) {
            switch (a->getElementByteSize()) {
              case 1:
                return llvm::ConstantDataArray::get(
                    dest_context, llvm::arrayRefFromStringRef(raw_data));
              case 2: {
                llvm::ArrayRef<uint16_t> ref(
                    reinterpret_cast<const uint16_t *>(raw_data.bytes_begin()),
                    reinterpret_cast<const uint16_t *>(raw_data.bytes_end()));
                return llvm::ConstantDataArray::get(dest_context, ref);
              }
              case 4: {
                llvm::ArrayRef<uint32_t> ref(
                    reinterpret_cast<const uint32_t *>(raw_data.bytes_begin()),
                    reinterpret_cast<const uint32_t *>(raw_data.bytes_end()));
                return llvm::ConstantDataArray::get(dest_context, ref);
              }
              case 8: {
                llvm::ArrayRef<uint64_t> ref(
                    reinterpret_cast<const uint64_t *>(raw_data.bytes_begin()),
                    reinterpret_cast<const uint64_t *>(raw_data.bytes_end()));
                return llvm::ConstantDataArray::get(dest_context, ref);
              }
            }
          } else if (el_type->isFloatTy()) {
            llvm::ArrayRef<float> ref(
                reinterpret_cast<const float *>(raw_data.bytes_begin()),
                reinterpret_cast<const float *>(raw_data.bytes_end()));
            return llvm::ConstantDataArray::get(dest_context, ref);
  
          } else if (el_type->isDoubleTy()) {
            llvm::ArrayRef<double> ref(
                reinterpret_cast<const double *>(raw_data.bytes_begin()),
                reinterpret_cast<const double *>(raw_data.bytes_end()));
            return llvm::ConstantDataArray::get(dest_context, ref);
          }
  
          LOG(FATAL) << "Unsupported element type in constant data array: "
                     << remill::LLVMThingToString(el_type);
          return nullptr;
        }
      } else if (auto v = llvm::dyn_cast<llvm::ConstantDataVector>(d); v) {
        if (in_same_context) {
          return v;
        } else {
          LOG(FATAL)
              << "Moving constant data vectors across contexts is not yet supported";
          return nullptr;
        }
  
      } else if (in_same_context) {
        LOG(ERROR) << "Not adapting constant when moving to destination module: "
                   << LLVMThingToString(c);
        return c;
  
      } else {
        LOG(FATAL) << "Cannot move constant to destination context: "
                   << LLVMThingToString(c);
        return nullptr;
      }
    } else if (auto ce = llvm::dyn_cast<llvm::ConstantExpr>(c)) {
      switch (ce->getOpcode()) {
        case llvm::Instruction::Add: {
          const auto b = llvm::dyn_cast<llvm::AddOperator>(ce);
          return llvm::ConstantExpr::getAdd(
              MoveConstantIntoModule(ce->getOperand(0), dest_module),
              MoveConstantIntoModule(ce->getOperand(1), dest_module),
              b->hasNoUnsignedWrap(), b->hasNoSignedWrap());
        }
        case llvm::Instruction::Sub: {
          const auto b = llvm::dyn_cast<llvm::SubOperator>(ce);
          return llvm::ConstantExpr::getSub(
              MoveConstantIntoModule(ce->getOperand(0), dest_module),
              MoveConstantIntoModule(ce->getOperand(1), dest_module),
              b->hasNoUnsignedWrap(), b->hasNoSignedWrap());
        }
        case llvm::Instruction::And:
          return llvm::ConstantExpr::getAnd(
              MoveConstantIntoModule(ce->getOperand(0), dest_module),
              MoveConstantIntoModule(ce->getOperand(1), dest_module));
        case llvm::Instruction::Or:
          return llvm::ConstantExpr::getOr(
              MoveConstantIntoModule(ce->getOperand(0), dest_module),
              MoveConstantIntoModule(ce->getOperand(1), dest_module));
        case llvm::Instruction::Xor:
          return llvm::ConstantExpr::getXor(
              MoveConstantIntoModule(ce->getOperand(0), dest_module),
              MoveConstantIntoModule(ce->getOperand(1), dest_module));
        case llvm::Instruction::ICmp:
          return llvm::ConstantExpr::getICmp(
              ce->getPredicate(),
              MoveConstantIntoModule(ce->getOperand(0), dest_module),
              MoveConstantIntoModule(ce->getOperand(1), dest_module));
        case llvm::Instruction::ZExt:
          return llvm::ConstantExpr::getZExt(
              MoveConstantIntoModule(ce->getOperand(0), dest_module), type);
        case llvm::Instruction::SExt:
          return llvm::ConstantExpr::getSExt(
              MoveConstantIntoModule(ce->getOperand(0), dest_module), type);
        case llvm::Instruction::Trunc:
          return llvm::ConstantExpr::getTrunc(
              MoveConstantIntoModule(ce->getOperand(0), dest_module), type);
        case llvm::Instruction::Select:
          return llvm::ConstantExpr::getSelect(
              MoveConstantIntoModule(ce->getOperand(0), dest_module),
              MoveConstantIntoModule(ce->getOperand(1), dest_module),
              MoveConstantIntoModule(ce->getOperand(2), dest_module));
        case llvm::Instruction::Shl: {
          const auto b = llvm::dyn_cast<llvm::ShlOperator>(ce);
          return llvm::ConstantExpr::getShl(
              MoveConstantIntoModule(ce->getOperand(0), dest_module),
              MoveConstantIntoModule(ce->getOperand(1), dest_module),
              b->hasNoUnsignedWrap(), b->hasNoSignedWrap());
        }
        case llvm::Instruction::LShr: {
          const auto b = llvm::dyn_cast<llvm::LShrOperator>(ce);
          return llvm::ConstantExpr::getLShr(
              MoveConstantIntoModule(ce->getOperand(0), dest_module),
              MoveConstantIntoModule(ce->getOperand(1), dest_module),
              b->isExact());
        }
        case llvm::Instruction::AShr: {
          const auto b = llvm::dyn_cast<llvm::AShrOperator>(ce);
          return llvm::ConstantExpr::getAShr(
              MoveConstantIntoModule(ce->getOperand(0), dest_module),
              MoveConstantIntoModule(ce->getOperand(1), dest_module),
              b->isExact());
        }
        case llvm::Instruction::UDiv: {
          const auto b = llvm::dyn_cast<llvm::UDivOperator>(ce);
          return llvm::ConstantExpr::getUDiv(
              MoveConstantIntoModule(ce->getOperand(0), dest_module),
              MoveConstantIntoModule(ce->getOperand(1), dest_module),
              b->isExact());
        }
        case llvm::Instruction::SDiv: {
          const auto b = llvm::dyn_cast<llvm::SDivOperator>(ce);
          return llvm::ConstantExpr::getSDiv(
              MoveConstantIntoModule(ce->getOperand(0), dest_module),
              MoveConstantIntoModule(ce->getOperand(1), dest_module),
              b->isExact());
        }
        case llvm::Instruction::URem:
          return llvm::ConstantExpr::getURem(
              MoveConstantIntoModule(ce->getOperand(0), dest_module),
              MoveConstantIntoModule(ce->getOperand(1), dest_module));
        case llvm::Instruction::SRem:
          return llvm::ConstantExpr::getSRem(
              MoveConstantIntoModule(ce->getOperand(0), dest_module),
              MoveConstantIntoModule(ce->getOperand(1), dest_module));
        case llvm::Instruction::IntToPtr:
          return llvm::ConstantExpr::getIntToPtr(
              MoveConstantIntoModule(ce->getOperand(0), dest_module), type);
        case llvm::Instruction::PtrToInt:
          return llvm::ConstantExpr::getPtrToInt(
              MoveConstantIntoModule(ce->getOperand(0), dest_module), type);
        case llvm::Instruction::BitCast:
          return llvm::ConstantExpr::getBitCast(
              MoveConstantIntoModule(ce->getOperand(0), dest_module), type);
        case llvm::Instruction::GetElementPtr: {
          const auto g = llvm::dyn_cast<llvm::GEPOperator>(ce);
          const auto ni = g->getNumIndices();
          const auto source_type = ::remill::RecontextualizeType(
              g->getSourceElementType(), dest_context);
          std::vector<llvm::Constant *> indices(ni);
          for (auto i = 0u; i < ni; ++i) {
            indices[i] =
                MoveConstantIntoModule(ce->getOperand(i + 1u), dest_module);
          }
          return llvm::ConstantExpr::getGetElementPtr(
              source_type, MoveConstantIntoModule(ce->getOperand(0), dest_module),
              indices, g->isInBounds(), g->getInRangeIndex());
        }
        default:
          if (in_same_context) {
            LOG(ERROR) << "Unsupported CE when moving across module boundaries: "
                       << LLVMThingToString(ce);
            return ce;
  
          } else {
            LOG(FATAL) << "Unsupported CE when moving across context boundaries: "
                       << LLVMThingToString(ce);
            return nullptr;
          }
      }
    } else if (auto ca = llvm::dyn_cast<llvm::ConstantAggregate>(c); ca) {
      if (auto a = llvm::dyn_cast<llvm::ConstantArray>(ca); a) {
        std::vector<llvm::Constant *> new_elems;
        new_elems.reserve(a->getNumOperands());
        for (auto it = a->op_begin(), end = a->op_end(); it != end; ++it) {
          new_elems.push_back(MoveConstantIntoModule(
              llvm::cast<llvm::Constant>(it->get()), dest_module));
        }
  
        return llvm::ConstantArray::get(llvm::cast<llvm::ArrayType>(type),
                                        new_elems);
  
      } else if (auto s = llvm::dyn_cast<llvm::ConstantStruct>(ca); s) {
        std::vector<llvm::Constant *> new_elems;
        new_elems.reserve(s->getNumOperands());
        for (auto it = s->op_begin(), end = s->op_end(); it != end; ++it) {
          new_elems.push_back(MoveConstantIntoModule(
              llvm::cast<llvm::Constant>(it->get()), dest_module));
        }
  
        return llvm::ConstantStruct::get(llvm::cast<llvm::StructType>(type),
                                         new_elems);
  
      } else if (auto v = llvm::dyn_cast<llvm::ConstantVector>(ca); v) {
        std::vector<llvm::Constant *> new_elems;
        new_elems.reserve(v->getNumOperands());
        for (auto it = v->op_begin(), end = v->op_end(); it != end; ++it) {
          new_elems.push_back(MoveConstantIntoModule(
              llvm::cast<llvm::Constant>(it->get()), dest_module));
        }
  
        return llvm::ConstantVector::get(new_elems);
  
      } else if (in_same_context) {
        LOG(ERROR) << "Unsupported CA when moving across module boundaries: "
                   << LLVMThingToString(c);
        return c;
  
      } else {
        LOG(FATAL) << "Unsupported CA when moving across context boundaries: "
                   << LLVMThingToString(c);
        return nullptr;
      }
  
    } else if (in_same_context) {
      LOG(ERROR) << "Unsupported constant when moving across module boundaries: "
                 << LLVMThingToString(c);
      return c;
  
    } else {
      LOG(FATAL) << "Unsupported constant when moving across context boundaries: "
                 << LLVMThingToString(c);
      return nullptr;
    }
  }
  
  llvm::GlobalVariable *DeclareVarInModule(llvm::GlobalVariable *var,
                                           llvm::Module *dest_module) {
    auto dest_var = dest_module->getGlobalVariable(var->getName());
    if (dest_var) {
      return dest_var;
    }
  
    auto type = var->getType()->getElementType();
    dest_var = new llvm::GlobalVariable(
        *dest_module, type, var->isConstant(), var->getLinkage(), nullptr,
        var->getName(), nullptr, var->getThreadLocalMode(),
        var->getType()->getAddressSpace());
  
    dest_var->copyAttributesFrom(var);
  
    if (var->hasInitializer() && var->hasLocalLinkage()) {
      auto initializer = var->getInitializer();
      dest_var->setInitializer(MoveConstantIntoModule(initializer, dest_module));
    } else {
      LOG_IF(FATAL, var->hasLocalLinkage())
          << "Cannot declare internal variable " << var->getName().str()
          << " as external in another module";
    }
  
    return dest_var;
  }
  
  
  llvm::GlobalAlias *DeclareAliasInModule(llvm::GlobalAlias *var,
                                          llvm::Module *dest_module) {
    for (auto &alias : dest_module->aliases()) {
      if (alias.getName() == var->getName()) {
        return &alias;
      }
    }
  
    auto type = var->getType()->getElementType();
    auto dest_var = llvm::GlobalAlias::create(
        type, var->getType()->getAddressSpace(), var->getLinkage(),
        var->getName(), MoveConstantIntoModule(var->getAliasee(), dest_module),
        dest_module);
  
    return dest_var;
  }
  
  }  // namespace
  
  // Clone function `source_func` into `dest_func`, using `value_map` to map over
  // values. This will strip out debug info during the clone. This will strip out
  // debug info during the clone.
  //
  // Note: this will try to clone globals referenced from the module of
  //       `source_func` into the module of `dest_func`.
  void CloneFunctionInto(llvm::Function *source_func, llvm::Function *dest_func,
                         ValueMap &value_map) {
  
    auto func_name = source_func->getName().str();
    auto source_mod = source_func->getParent();
    auto dest_mod = dest_func->getParent();
    auto &source_context = source_mod->getContext();
    auto &dest_context = dest_func->getContext();
    auto reg_md_id = source_context.getMDKindID("remill_register");
  
    // Make sure that when we're cloning `__remill_basic_block`, we don't
    // throw away register names and such.
  #if LLVM_VERSION_NUMBER >= LLVM_VERSION(3, 9)
    dest_func->getContext().setDiscardValueNames(false);
  #endif
  
    dest_func->setAttributes(source_func->getAttributes());
    dest_func->setLinkage(source_func->getLinkage());
    dest_func->setVisibility(source_func->getVisibility());
    dest_func->setCallingConv(source_func->getCallingConv());
  
  #if LLVM_VERSION_NUMBER >= LLVM_VERSION(3, 6)
    dest_func->setIsMaterializable(source_func->isMaterializable());
  #endif
  
    // Clone the basic blocks and their instructions.
    std::unordered_map<llvm::BasicBlock *, llvm::BasicBlock *> block_map;
    for (auto &old_block : *source_func) {
      auto new_block = llvm::BasicBlock::Create(dest_func->getContext(),
                                                old_block.getName(), dest_func);
      value_map[&old_block] = new_block;
      block_map[&old_block] = new_block;
  
      auto &new_insts = new_block->getInstList();
      for (auto &old_inst : old_block) {
        if (llvm::isa<llvm::DbgInfoIntrinsic>(old_inst)) {
          continue;
        }
  
        auto new_inst = old_inst.clone();
        new_insts.push_back(new_inst);
        value_map[&old_inst] = new_inst;
      }
    }
  
    llvm::SmallVector<std::pair<unsigned, llvm::MDNode *>, 4> mds;
  
    // Fixup the references in the cloned instructions so that they point into
    // the cloned function, or point to declared globals in the module containing
    // `dest_func`.
    for (auto &old_block : *source_func) {
      for (auto &old_inst : old_block) {
        if (llvm::isa<llvm::DbgInfoIntrinsic>(old_inst)) {
          continue;
        }
  
        auto new_inst = llvm::dyn_cast<llvm::Instruction>(value_map[&old_inst]);
  
        // Clear out all metadata from the new instruction.
  
        old_inst.getAllMetadata(mds);
        for (auto md_info : mds) {
          if (md_info.first != reg_md_id || &source_context != &dest_context) {
            new_inst->setMetadata(md_info.first, nullptr);
          }
        }
  
        new_inst->setDebugLoc(llvm::DebugLoc());
        new_inst->setName(old_inst.getName());
  
        for (auto &new_op : new_inst->operands()) {
          auto old_op_val = new_op.get();
  
          if (llvm::isa<llvm::Constant>(old_op_val) &&
              !llvm::isa<llvm::GlobalValue>(old_op_val)) {
            continue;  // Don't clone constants.
          }
  
          // Already cloned the value, replace the old with the new.
          auto new_op_val_it = value_map.find(old_op_val);
          if (value_map.end() != new_op_val_it) {
            new_op.set(new_op_val_it->second);
            continue;
          }
  
          // At this point, all we should have is a global.
          auto global_val = llvm::dyn_cast<llvm::GlobalValue>(old_op_val);
          if (!global_val) {
            LOG(FATAL) << "Cannot clone value " << LLVMThingToString(old_op_val)
                       << " from function " << func_name << " because it isn't "
                       << "a global value.";
          }
  
          // If it's a global and we're in the same module, then use it.
          if (global_val && dest_mod == source_mod) {
            value_map[global_val] = global_val;
            new_op.set(global_val);
            continue;
          }
  
          // Declare the global in the new module.
          llvm::GlobalValue *new_global_val = nullptr;
  
          if (auto global_val_func = llvm::dyn_cast<llvm::Function>(global_val);
              global_val_func) {
            auto new_func = dest_mod->getOrInsertFunction(
                global_val->getName(),
                llvm::dyn_cast<llvm::FunctionType>(GetValueType(global_val)));
  
            new_global_val = llvm::dyn_cast<llvm::GlobalValue>(
                new_func IF_LLVM_GTE_900(.getCallee()));
  
            if (auto as_func = llvm::dyn_cast<llvm::Function>(new_global_val)) {
              as_func->setAttributes(global_val_func->getAttributes());
            }
  
          } else if (auto global_val_var =
                         llvm::dyn_cast<llvm::GlobalVariable>(global_val);
                     global_val_var) {
            const auto new_global_val_var =
                llvm::dyn_cast<llvm::GlobalVariable>(dest_mod->getOrInsertGlobal(
                    global_val->getName(), GetValueType(global_val)));
            if (new_global_val_var != global_val_var &&
                global_val_var->hasInitializer()) {
              new_global_val_var->setInitializer(MoveConstantIntoModule(
                  global_val_var->getInitializer(), dest_mod));
            }
  
            new_global_val = new_global_val_var;
  
          } else {
            LOG(FATAL) << "Cannot clone value " << LLVMThingToString(old_op_val)
                       << " into new module for function " << func_name;
          }
  
          auto old_name = global_val->getName().str();
          auto new_name = new_global_val->getName().str();
  
          CHECK(new_global_val->getName() == global_val->getName())
              << "Name of cloned global value declaration for " << old_name
              << "does not match global value definition of " << new_name
              << " in the source module. The cloned value probably has the "
              << "same name as another value in the dest module, but with a "
              << "different type.";
  
          // Mark the global as extern, so that it can link back to the old
          // module.
          new_global_val->setLinkage(llvm::GlobalValue::ExternalLinkage);
          new_global_val->setVisibility(llvm::GlobalValue::DefaultVisibility);
  
          value_map[global_val] = new_global_val;
          new_op.set(new_global_val);
        }
  
        // Remap PHI node predecessor blocks.
        if (auto phi = llvm::dyn_cast<llvm::PHINode>(new_inst)) {
          for (auto i = 0UL; i < phi->getNumIncomingValues(); ++i) {
            phi->setIncomingBlock(i, block_map[phi->getIncomingBlock(i)]);
          }
        }
      }
    }
  }
  
  // Move a function from one module into another module.
  //
  // TODO(pag): Make this work across distinct `llvm::LLVMContext`s.
  void MoveFunctionIntoModule(llvm::Function *func, llvm::Module *dest_module) {
    const auto source_context = &(func->getContext());
    const auto dest_context = &(dest_module->getContext());
    CHECK(source_context == dest_context)
        << "Cannot move function across two independent LLVM contexts.";
  
    auto source_module = func->getParent();
    CHECK(source_module != dest_module)
        << "Cannot move function to the same module.";
  
    auto existing = dest_module->getFunction(func->getName());
    if (existing) {
      CHECK(existing->isDeclaration())
          << "Function " << func->getName().str()
          << " already exists in destination module.";
      existing->setName(llvm::Twine::createNull());
      existing->setLinkage(llvm::GlobalValue::PrivateLinkage);
      existing->setVisibility(llvm::GlobalValue::DefaultVisibility);
    }
  
    const auto in_same_context = source_context == dest_context;
  
    if (in_same_context) {
      func->removeFromParent();
      dest_module->getFunctionList().push_back(func);
    }
  
    if (existing) {
      existing->replaceAllUsesWith(func);
      existing->eraseFromParent();
      existing = nullptr;
    }
  
    if (!in_same_context) {
      IF_LLVM_GTE_370(ClearMetaData(func);)
    }
  
    for (auto &block : *func) {
      for (auto &inst : block) {
  
        if (!in_same_context) {
          ClearMetaData(&inst);
        }
  
        // Substitute globals in the operands.
        for (auto &op : inst.operands()) {
          if (auto c = llvm::dyn_cast<llvm::Constant>(op.get()); c) {
            op.set(MoveConstantIntoModule(c, dest_module));
          }
        }
  
        if (auto cs = compat::llvm::CallSite(&inst)) {
          if (auto callee = cs.getCalledFunction();
              callee && callee->getParent() != dest_module) {
            cs.setCalledFunction(DeclareFunctionInModule(callee, dest_module));
          }
        }
      }
    }
  }
  
  namespace {
  
  static llvm::Type *
  RecontextualizeType(llvm::Type *type, llvm::LLVMContext &context,
                      std::unordered_map<llvm::Type *, llvm::Type *> &cache) {
    auto &cached = cache[type];
    if (cached) {
      return cached;
    }
  
    switch (type->getTypeID()) {
      case llvm::Type::VoidTyID: return llvm::Type::getVoidTy(context);
      case llvm::Type::HalfTyID: return llvm::Type::getHalfTy(context);
      case llvm::Type::FloatTyID: return llvm::Type::getFloatTy(context);
      case llvm::Type::DoubleTyID: return llvm::Type::getDoubleTy(context);
      case llvm::Type::X86_FP80TyID: return llvm::Type::getX86_FP80Ty(context);
      case llvm::Type::FP128TyID: return llvm::Type::getFP128Ty(context);
      case llvm::Type::PPC_FP128TyID: return llvm::Type::getPPC_FP128Ty(context);
      case llvm::Type::LabelTyID: return llvm::Type::getLabelTy(context);
      case llvm::Type::MetadataTyID: return llvm::Type::getMetadataTy(context);
      case llvm::Type::X86_MMXTyID: return llvm::Type::getX86_MMXTy(context);
      case llvm::Type::TokenTyID: return llvm::Type::getTokenTy(context);
      case llvm::Type::IntegerTyID: {
        auto int_type = llvm::dyn_cast<llvm::IntegerType>(type);
        cached =
            llvm::IntegerType::get(context, int_type->getPrimitiveSizeInBits());
        break;
      }
      case llvm::Type::FunctionTyID: {
        auto func_type = llvm::dyn_cast<llvm::FunctionType>(type);
        auto ret_type =
            RecontextualizeType(func_type->getReturnType(), context, cache);
        llvm::SmallVector<llvm::Type *, 4> param_types;
        for (auto param_type : func_type->params()) {
          param_types.push_back(RecontextualizeType(param_type, context, cache));
        }
        cached =
            llvm::FunctionType::get(ret_type, param_types, func_type->isVarArg());
        break;
      }
  
      case llvm::Type::StructTyID: {
        auto struct_type = llvm::dyn_cast<llvm::StructType>(type);
        auto new_struct_type =
            llvm::StructType::create(context, struct_type->getName());
        cached = new_struct_type;
  
        llvm::SmallVector<llvm::Type *, 4> elem_types;
        for (auto elem_type : struct_type->elements()) {
          elem_types.push_back(RecontextualizeType(elem_type, context, cache));
        }
  
        if (elem_types.size()) {
          new_struct_type->setBody(elem_types, struct_type->isPacked());
        }
  
        return new_struct_type;
      }
  
      case llvm::Type::ArrayTyID: {
        auto arr_type = llvm::dyn_cast<llvm::ArrayType>(type);
        auto elem_type = arr_type->getElementType();
        cached =
            llvm::ArrayType::get(RecontextualizeType(elem_type, context, cache),
                                 arr_type->getNumElements());
        break;
      }
  
      case llvm::Type::PointerTyID: {
        auto ptr_type = llvm::dyn_cast<llvm::PointerType>(type);
        auto elem_type = ptr_type->getElementType();
        cached =
            llvm::PointerType::get(RecontextualizeType(elem_type, context, cache),
                                   ptr_type->getAddressSpace());
        break;
      }
  
      case llvm::GetFixedVectorTypeId(): {
        auto arr_type = llvm::dyn_cast<llvm::FixedVectorType>(type);
        auto elem_type = arr_type->getElementType();
        cached = llvm::FixedVectorType::get(
            RecontextualizeType(elem_type, context, cache),
            arr_type->getNumElements());
        break;
      }
  
      default:
        LOG(FATAL) << "Unable to recontextualize type "
                   << LLVMThingToString(type);
        return nullptr;
    }
  
    return cached;
  }
  
  }  // namespace
  
  // Get an instance of `type` that belongs to `context`.
  llvm::Type *RecontextualizeType(llvm::Type *type, llvm::LLVMContext &context) {
    if (&(type->getContext()) == &context) {
      return type;
    }
  
    std::unordered_map<llvm::Type *, llvm::Type *> cache;
    return RecontextualizeType(type, context, cache);
  }
  
  // Produce a sequence of instructions that will load values from
  // memory, building up the correct type. This will invoke the various
  // memory read intrinsics in order to match the right type, or
  // recursively build up the right type.
  llvm::Value *LoadFromMemory(const IntrinsicTable &intrinsics,
                              llvm::BasicBlock *block, llvm::Type *type,
                              llvm::Value *mem_ptr, llvm::Value *addr) {
  
    const auto initial_addr = addr;
    auto module = intrinsics.error->getParent();
    auto &context = module->getContext();
    llvm::DataLayout dl(module);
    llvm::Value *args_2[2] = {mem_ptr, addr};
    auto index_type = llvm::Type::getIntNTy(context, dl.getPointerSizeInBits(0));
  
    llvm::IRBuilder<> ir(block);
  
    switch (type->getTypeID()) {
      case llvm::Type::HalfTyID: {
        llvm::Type *types[] = {llvm::Type::getFloatTy(context)};
        auto converter = llvm::Intrinsic::getDeclaration(
            module, llvm::Intrinsic::convert_from_fp16, types);
        llvm::Value *conv_args[] = {
            ir.CreateCall(intrinsics.read_memory_16, args_2)};
        return ir.CreateFPTrunc(ir.CreateCall(converter, conv_args), type);
      }
  
      case llvm::Type::FloatTyID:
        return ir.CreateCall(intrinsics.read_memory_f32, args_2);
  
      case llvm::Type::DoubleTyID:
        return ir.CreateCall(intrinsics.read_memory_f64, args_2);
  
      case llvm::Type::X86_FP80TyID:
        return ir.CreateFPExt(ir.CreateCall(intrinsics.read_memory_f80, args_2),
                              type);
  
      case llvm::Type::X86_MMXTyID:
        return ir.CreateBitCast(ir.CreateCall(intrinsics.read_memory_64, args_2),
                                type);
  
      case llvm::Type::IntegerTyID:
        switch (dl.getTypeAllocSize(type)) {
          case 1: return ir.CreateCall(intrinsics.read_memory_8, args_2);
          case 2: return ir.CreateCall(intrinsics.read_memory_16, args_2);
          case 4: return ir.CreateCall(intrinsics.read_memory_32, args_2);
          case 8: return ir.CreateCall(intrinsics.read_memory_64, args_2);
          default: break;
        }
        [[clang::fallthrough]];
  
      case llvm::Type::FP128TyID:
      case llvm::Type::PPC_FP128TyID: {
        const auto size = dl.getTypeAllocSize(type);
        auto res = ir.CreateAlloca(type);
        auto i8_type = llvm::Type::getInt8Ty(context);
        auto byte_array =
            ir.CreateBitCast(res, llvm::PointerType::get(i8_type, 0));
        llvm::Value *gep_indices[2] = {
            llvm::ConstantInt::get(index_type, 0, false), nullptr};
  
        // Load one byte at a time from memory, and store it into
        // `res`.
        for (auto i = 0U; i < size; ++i) {
          args_2[1] = ir.CreateAdd(
              addr, llvm::ConstantInt::get(addr->getType(), i, false));
          auto byte = ir.CreateCall(intrinsics.read_memory_8, args_2);
          gep_indices[1] = llvm::ConstantInt::get(index_type, i, false);
          auto byte_ptr = ir.CreateInBoundsGEP(type, byte_array, gep_indices);
          ir.CreateStore(byte, byte_ptr);
        }
  
        return ir.CreateLoad(res);
      }
  
      // Building up a structure requires us to start with an undef value,
      // then inject each element value one at a time.
      case llvm::Type::StructTyID: {
        const auto struct_type = llvm::dyn_cast<llvm::StructType>(type);
        const auto layout = dl.getStructLayout(struct_type);
        llvm::Value *val = llvm::UndefValue::get(type);
        const auto num_elems = struct_type->getNumElements();
        for (auto i = 0u; i < num_elems; ++i) {
          const auto elem_type = struct_type->getStructElementType(i);
          const auto offset = layout->getElementOffset(i);
          addr = ir.CreateAdd(initial_addr, llvm::ConstantInt::get(
                                                addr->getType(), offset, false));
          auto elem_val =
              LoadFromMemory(intrinsics, block, elem_type, mem_ptr, addr);
          ir.SetInsertPoint(block);
          unsigned indexes[] = {i};
          val = ir.CreateInsertValue(val, elem_val, indexes);
        }
        return val;
      }
  
      // Build up the array in the same was as we do with structures.
      case llvm::Type::ArrayTyID: {
        auto arr_type = llvm::dyn_cast<llvm::ArrayType>(type);
        const auto num_elems = arr_type->getNumElements();
        const auto elem_type = arr_type->getElementType();
        const auto elem_size = dl.getTypeAllocSize(elem_type);
        llvm::Value *val = llvm::UndefValue::get(type);
  
        for (uint64_t index = 0, offset = 0; index < num_elems;
             ++index, offset += elem_size) {
          addr = ir.CreateAdd(initial_addr, llvm::ConstantInt::get(
                                                addr->getType(), offset, false));
          unsigned indexes[] = {static_cast<unsigned>(index)};
          auto elem_val =
              LoadFromMemory(intrinsics, block, elem_type, mem_ptr, addr);
          ir.SetInsertPoint(block);
          val = ir.CreateInsertValue(val, elem_val, indexes);
        }
        return val;
      }
  
      // Read pointers from memory by loading the correct sized integer,
      // then casting it to a pointer.
      case llvm::Type::PointerTyID: {
        auto ptr_type = llvm::dyn_cast<llvm::PointerType>(type);
        auto size_bits = dl.getTypeAllocSizeInBits(ptr_type);
        auto intptr_type =
            llvm::IntegerType::get(context, static_cast<unsigned>(size_bits));
        auto addr_val =
            LoadFromMemory(intrinsics, block, intptr_type, mem_ptr, addr);
        ir.SetInsertPoint(block);
        return ir.CreateIntToPtr(addr_val, ptr_type);
      }
  
      // Build up the vector in the nearly the same was as we do with arrays.
      case llvm::GetFixedVectorTypeId(): {
        auto vec_type = llvm::dyn_cast<llvm::FixedVectorType>(type);
        const auto num_elems = vec_type->getNumElements();
        const auto elem_type = vec_type->getElementType();
        const auto elem_size = dl.getTypeAllocSize(elem_type);
        llvm::Value *val = llvm::UndefValue::get(type);
  
        for (uint64_t index = 0, offset = 0; index < num_elems;
             ++index, offset += elem_size) {
          addr = ir.CreateAdd(initial_addr, llvm::ConstantInt::get(
                                                addr->getType(), offset, false));
          auto elem_val =
              LoadFromMemory(intrinsics, block, elem_type, mem_ptr, addr);
          ir.SetInsertPoint(block);
          val =
              ir.CreateInsertElement(val, elem_val, static_cast<unsigned>(index));
        }
        return val;
      }
  
      case llvm::Type::VoidTyID:
      case llvm::Type::LabelTyID:
      case llvm::Type::MetadataTyID:
      case llvm::Type::TokenTyID:
      case llvm::Type::FunctionTyID:
      default:
        LOG(FATAL) << "Unable to produce IR sequence to load type "
                   << remill::LLVMThingToString(type) << " from memory";
        return nullptr;
    }
  }
  
  // Produce a sequence of instructions that will store a value to
  // memory. This will invoke the various memory write intrinsics
  // in order to match the right type, or recursively destructure
  // the type into components which can be written to memory.
  //
  // Returns the new value of the memory pointer.
  llvm::Value *StoreToMemory(const IntrinsicTable &intrinsics,
                             llvm::BasicBlock *block, llvm::Value *val_to_store,
                             llvm::Value *mem_ptr, llvm::Value *addr) {
  
    const auto initial_addr = addr;
    auto module = intrinsics.error->getParent();
    auto &context = module->getContext();
    llvm::DataLayout dl(module);
    llvm::Value *args_3[3] = {mem_ptr, addr, val_to_store};
    auto index_type = llvm::Type::getInt32Ty(context);
  
    llvm::IRBuilder<> ir(block);
  
    auto type = val_to_store->getType();
    switch (type->getTypeID()) {
      case llvm::Type::HalfTyID: {
        llvm::Type *types[] = {llvm::Type::getFloatTy(context)};
        auto converter = llvm::Intrinsic::getDeclaration(
            module, llvm::Intrinsic::convert_to_fp16, types);
        llvm::Value *conv_args[] = {
            ir.CreateFPExt(val_to_store, llvm::Type::getFloatTy(context))};
        args_3[2] = ir.CreateCall(converter, conv_args);
  
        return ir.CreateCall(intrinsics.write_memory_16, args_3);
      }
  
      case llvm::Type::FloatTyID:
        return ir.CreateCall(intrinsics.write_memory_f32, args_3);
  
      case llvm::Type::DoubleTyID:
        return ir.CreateCall(intrinsics.write_memory_f64, args_3);
  
      case llvm::Type::X86_FP80TyID: {
        auto double_type = llvm::Type::getDoubleTy(context);
        args_3[2] = ir.CreateFPTrunc(val_to_store, double_type);
        return ir.CreateCall(intrinsics.write_memory_f80, args_3);
      }
  
      case llvm::Type::X86_MMXTyID: {
        auto i64_type = llvm::Type::getInt64Ty(context);
        args_3[2] = ir.CreateBitCast(val_to_store, i64_type);
        return ir.CreateCall(intrinsics.write_memory_64, args_3);
      }
  
      case llvm::Type::IntegerTyID:
        switch (dl.getTypeAllocSize(type)) {
          case 1: return ir.CreateCall(intrinsics.write_memory_8, args_3);
          case 2: return ir.CreateCall(intrinsics.write_memory_16, args_3);
          case 4: return ir.CreateCall(intrinsics.write_memory_32, args_3);
          case 8: return ir.CreateCall(intrinsics.write_memory_64, args_3);
          default: break;
        }
        [[clang::fallthrough]];
  
      case llvm::Type::FP128TyID:
      case llvm::Type::PPC_FP128TyID: {
        const auto size = dl.getTypeAllocSize(type);
  
        // Stack-allocate the value, so we can pull out one byte
        // at a time from it, and then write it into the target
        // address space.
        auto res = ir.CreateAlloca(type);
        ir.CreateStore(val_to_store, res);
  
        auto i8_type = llvm::Type::getInt8Ty(context);
        auto byte_array =
            ir.CreateBitCast(res, llvm::PointerType::get(i8_type, 0));
        llvm::Value *gep_indices[2] = {
            llvm::ConstantInt::get(index_type, 0, false), nullptr};
  
        // Store one byte at a time to memory.
        for (auto i = 0U; i < size; ++i) {
          args_3[1] = ir.CreateAdd(
              addr, llvm::ConstantInt::get(addr->getType(), i, false));
          gep_indices[1] = llvm::ConstantInt::get(index_type, i, false);
          auto byte_ptr = ir.CreateInBoundsGEP(type, byte_array, gep_indices);
          args_3[2] = ir.CreateLoad(byte_ptr);
          args_3[0] = ir.CreateCall(intrinsics.write_memory_8, args_3);
        }
  
        return args_3[0];
      }
  
      // Store a structure by storing the individual elements of the structure.
      case llvm::Type::StructTyID: {
        auto struct_type = llvm::dyn_cast<llvm::StructType>(type);
        const auto layout = dl.getStructLayout(struct_type);
        const auto num_elems = struct_type->getNumElements();
        for (auto i = 0u; i < num_elems; ++i) {
          const auto offset = layout->getElementOffset(i);
          const auto elem_addr = ir.CreateAdd(
              initial_addr,
              llvm::ConstantInt::get(addr->getType(), offset, false));
          unsigned indexes[] = {i};
          const auto elem_val = ir.CreateExtractValue(val_to_store, indexes);
          mem_ptr =
              StoreToMemory(intrinsics, block, elem_val, mem_ptr, elem_addr);
          ir.SetInsertPoint(block);
        }
        return mem_ptr;
      }
  
      // Build up the array store in the same was as we do with structures.
      case llvm::Type::ArrayTyID: {
        auto arr_type = llvm::dyn_cast<llvm::ArrayType>(type);
        const auto num_elems = arr_type->getNumElements();
        const auto elem_type = arr_type->getElementType();
        const auto elem_size = dl.getTypeAllocSize(elem_type);
  
        for (uint64_t index = 0, offset = 0; index < num_elems;
             ++index, offset += elem_size) {
  
          auto elem_addr = ir.CreateAdd(
              initial_addr,
              llvm::ConstantInt::get(addr->getType(), offset, false));
          unsigned indexes[] = {static_cast<unsigned>(index)};
          auto elem_val = ir.CreateExtractValue(val_to_store, indexes);
          mem_ptr =
              StoreToMemory(intrinsics, block, elem_val, mem_ptr, elem_addr);
          ir.SetInsertPoint(block);
          offset += elem_size;
          index += 1;
        }
        return mem_ptr;
      }
  
      // Write pointers to memory by converting to the correct sized integer,
      // then storing that
      case llvm::Type::PointerTyID: {
        auto ptr_type = llvm::dyn_cast<llvm::PointerType>(type);
        auto size_bits = dl.getTypeAllocSizeInBits(ptr_type);
        auto intptr_type =
            llvm::IntegerType::get(context, static_cast<unsigned>(size_bits));
        return StoreToMemory(intrinsics, block,
                             ir.CreatePtrToInt(val_to_store, intptr_type),
                             mem_ptr, addr);
      }
  
      // Build up the vector store in the nearly the same was as we do with arrays.
      case llvm::GetFixedVectorTypeId(): {
        auto vec_type = llvm::dyn_cast<llvm::FixedVectorType>(type);
        const auto num_elems = vec_type->getNumElements();
        const auto elem_type = vec_type->getElementType();
        const auto elem_size = dl.getTypeAllocSize(elem_type);
  
        for (uint64_t index = 0, offset = 0; index < num_elems;
             ++index, offset += elem_size) {
  
          auto elem_addr = ir.CreateAdd(
              initial_addr,
              llvm::ConstantInt::get(addr->getType(), offset, false));
          auto elem_val =
              ir.CreateExtractElement(val_to_store, static_cast<unsigned>(index));
          mem_ptr =
              StoreToMemory(intrinsics, block, elem_val, mem_ptr, elem_addr);
          ir.SetInsertPoint(block);
          offset += elem_size;
          index += 1;
        }
  
        return mem_ptr;
      }
  
      case llvm::Type::VoidTyID:
      case llvm::Type::LabelTyID:
      case llvm::Type::MetadataTyID:
      case llvm::Type::TokenTyID:
      case llvm::Type::FunctionTyID:
      default:
        LOG(FATAL) << "Unable to produce IR sequence to store type "
                   << remill::LLVMThingToString(type) << " to memory";
        return nullptr;
    }
  }
  
  // Create an array of index values to pass to a GetElementPtr instruction
  // that will let us locate a particular register. Returns the final offset
  // into `type` which was reached as the first value in the pair, and the type
  // of what is at that offset in the second value of the pair.
  std::pair<size_t, llvm::Type *>
  BuildIndexes(const llvm::DataLayout &dl, llvm::Type *type, size_t offset,
               const size_t goal_offset,
               llvm::SmallVectorImpl<llvm::Value *> &indexes_out) {
  
    CHECK_LE(offset, goal_offset);
    CHECK_LE(goal_offset, (offset + dl.getTypeAllocSize(type)));
  
    size_t index = 0;
    const auto index_type = indexes_out[0]->getType();
  
    if (const auto struct_type = llvm::dyn_cast<llvm::StructType>(type);
        struct_type) {
  
      auto layout = dl.getStructLayout(struct_type);
      auto prev_elem_offset = 0;
      llvm::Type *prev_elem_type = nullptr;
  
      for (auto i = 0u, max_i = struct_type->getNumElements(); i < max_i; ++i) {
        auto elem_offset = layout->getElementOffset(i);
        auto elem_type = struct_type->getStructElementType(i);
        auto elem_size = dl.getTypeStoreSize(elem_type);
  
        // The goal offset comes after this element.
        if ((offset + elem_offset + elem_size) <= goal_offset) {
          prev_elem_offset = elem_offset;
          prev_elem_type = elem_type;
          continue;
  
        // Indexing into the `i`th element.
        } else if ((offset + elem_offset) <= goal_offset) {
          indexes_out.push_back(llvm::ConstantInt::get(index_type, i, false));
          return BuildIndexes(dl, elem_type, offset + elem_offset, goal_offset,
                              indexes_out);
  
        // We're indexing into some padding before the current element.
        } else if (i) {
          indexes_out.push_back(llvm::ConstantInt::get(index_type, i - 1, false));
          return {offset + prev_elem_offset, prev_elem_type};
  
        // We're indexing into some padding at the beginning of this structure.
        } else {
          return {offset, type};
        }
      }
  
    } else if (auto seq_type = llvm::dyn_cast<llvm::ArrayType>(type); seq_type) {
      const auto elem_type = seq_type->getElementType();
      const auto elem_size = dl.getTypeAllocSize(elem_type);
      const auto num_elems = seq_type->getNumElements();
  
      while ((offset + elem_size) <= goal_offset && index < num_elems) {
        offset += elem_size;
        index += 1;
      }
  
      CHECK_LE(offset, goal_offset);
      CHECK_LE(goal_offset, (offset + elem_size));
  
      indexes_out.push_back(llvm::ConstantInt::get(index_type, index, false));
      return BuildIndexes(dl, elem_type, offset, goal_offset, indexes_out);
    } else if (auto fvt_type = llvm::dyn_cast<llvm::FixedVectorType>(type); fvt_type) {
      // It is possible that this gets called on an unexpected type
      // such as FixedVectorType; if so, report the issue and fix if/when it
      // happens
      LOG(FATAL) << "Called BuildIndexes on unsupported type: "
                 << remill::LLVMThingToString(type);
  #if LLVM_VERSION_NUMBER >= LLVM_VERSION(11, 0)
    } else if (auto svt_type = llvm::dyn_cast<llvm::ScalableVectorType>(type); svt_type) {
      // same as above, but for scalable vectors
      LOG(FATAL) << "Called BuildIndexes on unsupported type: "
                 << remill::LLVMThingToString(type);
  #endif
    }
  
    return {offset, type};
  }
  
  // Given a pointer, `ptr`, and a goal byte offset to which we'd like to index,
  // build either a constant expression or sequence of instructions that can
  // index to that offset. `ir` is provided to support the instruction case
  // and to give access to a module for data layouts.
  llvm::Value *BuildPointerToOffset(llvm::IRBuilder<> &ir, llvm::Value *ptr,
                                    size_t dest_elem_offset,
                                    llvm::Type *dest_ptr_type_) {
  
    const auto block = ir.GetInsertBlock();
    const auto module = block->getModule();
    auto &context = block->getContext();
    const auto i32_type = llvm::Type::getInt32Ty(context);
  
    const auto &dl = module->getDataLayout();
    llvm::SmallVector<llvm::Value *, 16> indexes;
  
    auto ptr_type = llvm::dyn_cast<llvm::PointerType>(ptr->getType());
    CHECK_NOTNULL(ptr_type);
    const auto dest_elem_ptr_type =
        llvm::dyn_cast<llvm::PointerType>(dest_ptr_type_);
    CHECK_NOTNULL(dest_elem_ptr_type);
    auto ptr_addr_space = ptr_type->getAddressSpace();
    const auto dest_ptr_addr_space = dest_elem_ptr_type->getAddressSpace();
    auto constant_ptr = llvm::dyn_cast<llvm::Constant>(ptr);
  
    // Change address spaces if necessary before indexing.
    if (dest_ptr_addr_space != ptr_addr_space) {
      ptr_type = llvm::PointerType::get(ptr_type->getPointerElementType(),
                                        dest_ptr_addr_space);
      ptr_addr_space = dest_ptr_addr_space;
  
      if (constant_ptr) {
        constant_ptr =
            llvm::ConstantExpr::getAddrSpaceCast(constant_ptr, ptr_type);
        ptr = constant_ptr;
      } else {
        ptr = ir.CreateAddrSpaceCast(ptr, ptr_type);
      }
    }
  
    const auto dest_elem_type = dest_elem_ptr_type->getElementType();
    const auto ptr_elem_type = ptr_type->getElementType();
    const auto ptr_elem_size = dl.getTypeAllocSize(ptr_elem_type);
    const auto base_index = dest_elem_offset / ptr_elem_size;
  
    indexes.push_back(llvm::ConstantInt::get(i32_type, base_index, false));
  
    dest_elem_offset = dest_elem_offset % ptr_elem_size;
  
    auto [reached_disp, indexed_type] =
        BuildIndexes(dl, ptr_elem_type, 0, dest_elem_offset, indexes);
  
    if (reached_disp) {
      if (constant_ptr) {
        if (base_index) {
          constant_ptr = llvm::ConstantExpr::getGetElementPtr(
              ptr_elem_type, constant_ptr, indexes);
        } else {
          constant_ptr = llvm::ConstantExpr::getGetElementPtr(
              ptr_elem_type, constant_ptr, indexes, true,
              (base_index * ptr_elem_size) + reached_disp);
        }
        ptr = constant_ptr;
      } else {
        if (base_index) {
          ptr = ir.CreateGEP(ptr_elem_type, ptr, indexes);
        } else {
          ptr = ir.CreateInBoundsGEP(ptr_elem_type, ptr, indexes);
        }
      }
    }
  
    if (const auto diff = dest_elem_offset - reached_disp; diff) {
      DCHECK_LT(diff, dest_elem_offset);
      DCHECK_LT(diff, dl.getTypeAllocSize(indexed_type));
      const auto i8_type = llvm::Type::getInt8Ty(context);
      const auto i8_ptr_type =
          llvm::PointerType::getInt8PtrTy(context, ptr_addr_space);
  
      const auto dest_elem_size = dl.getTypeAllocSize(dest_elem_type);
      if (diff % dest_elem_size) {
        if (constant_ptr) {
          constant_ptr =
              llvm::ConstantExpr::getBitCast(constant_ptr, i8_ptr_type);
          constant_ptr = llvm::ConstantExpr::getGetElementPtr(
              i8_type, constant_ptr, llvm::ConstantInt::get(i32_type, diff));
          return llvm::ConstantExpr::getBitCast(constant_ptr, dest_elem_ptr_type);
  
        } else {
          ptr = ir.CreateBitCast(ptr, i8_ptr_type);
          ptr = ir.CreateGEP(i8_type, ptr,
                             llvm::ConstantInt::get(i32_type, diff, false));
          return ir.CreateBitCast(ptr, dest_elem_ptr_type);
        }
      } else {
        if (constant_ptr) {
          constant_ptr =
              llvm::ConstantExpr::getBitCast(constant_ptr, dest_elem_ptr_type);
          return llvm::ConstantExpr::getGetElementPtr(
              dest_elem_type, constant_ptr,
              llvm::ConstantInt::get(i32_type, diff / dest_elem_size));
        } else {
          ptr = ir.CreateBitCast(ptr, dest_elem_ptr_type);
          return ir.CreateGEP(
              dest_elem_type, ptr,
              llvm::ConstantInt::get(i32_type, diff / dest_elem_size, false));
        }
      }
    }
  
    if (constant_ptr) {
      return llvm::ConstantExpr::getBitCast(constant_ptr, dest_elem_ptr_type);
    } else {
      return ir.CreateBitCast(ptr, dest_elem_ptr_type);
    }
  }
  
  
  // Compute the total offset of a GEP chain.
  std::pair<llvm::Value *, int64_t>
  StripAndAccumulateConstantOffsets(const llvm::DataLayout &dl,
                                    llvm::Value *base) {
    const auto ptr_size = dl.getPointerSizeInBits(0);
    int64_t total_offset = 0;
    while (base) {
      if (auto gep = llvm::dyn_cast<llvm::GEPOperator>(base); gep) {
        llvm::APInt accumulated_offset(ptr_size, 0, false);
        if (!gep->accumulateConstantOffset(dl, accumulated_offset)) {
          break;
        }
  
        const auto curr_offset = accumulated_offset.getSExtValue();
        total_offset += curr_offset;
  
        base = gep->getPointerOperand();
  
      } else if (auto bc = llvm::dyn_cast<llvm::BitCastOperator>(base); bc) {
        base = bc->getOperand(0);
  
      } else if (auto itp = llvm::dyn_cast<llvm::IntToPtrInst>(base); itp) {
        base = itp->getOperand(0);
  
      } else if (auto pti = llvm::dyn_cast<llvm::PtrToIntOperator>(base); pti) {
        base = pti->getOperand(0);
  
      } else {
        break;
      }
    }
    return {base, total_offset};
  }
  
  }  // namespace remill
  