compor / pedigree

LLVM dependence graphs

Pedigree - Program Dependence Graph pass

Introduction

This is a LLVM opt pass for creating Program Dependence Graphs.

Features

• Out-of-source builds thanks to cmake.
• In-tree LLVM builds.

Requirements

• cmake 3.2.0 or later
• C++ compilers:
  • LLVM tested with:
    • 7.0.0
  • GCC tested with:
    • 7.3.1
• Boost tested with: - 1.68
• googletest tested with:
  • 1.8.0

External dependencies

Mandatory

• cmake-utils Used for supporting the cmake-based build system. Using git clone --recursive should take care of everything.
• sanitizers-cmake Used to provide support for sanitizers. Although the subproject is required for successful configuration, its use is optional.

Optional

None.

How to build

1. git clone --recursive this repo.
2. Create a directory for an out-of-source build and cd into it.
3. Run cmake and cmake --build . with that appropriate options. For examples on the various options have a look at the build scripts (provided for convenience) located in the utils/scripts/build subdirectory.

• compiler selection is catered by the exports_local_* scripts using the CC and CXX variables for my current machine, so adjust appropriately for your setup.
• export one of the exports_deps_* scripts, depending on the kind of setup you are interested in.

4. Optionally, you can install the pass by

cmake -DCMAKE_INSTALL_PREFIX=[path-to-install] -P cmake_install.cmake

Omitting CMAKE_INSTALL_PREFIX will use the ../install/ directory relative to the build directory.

5. lit-based tests can be run with cmake --build . --target check
6. googletest-based unit tests can be run with ./run_unit_tests.sh (see the script for details).

How to execute

Using opt

opt -load [path to plugin]/libLLVMPedigreePass.so -pedigree foo.bc -o foo.out.bc

Using clang

clang -Xclang -load -Xclang [path to plugin]/libLLVMPedigreePass.so foo.c -o foo

Notes

Customizing

A first step towards customization is to search for the pattern [Ss]keleton] and replace as with the desired name. A general good approach is to prefix everything with the name of the pass, especially in languages that do not offer some sort of namespace capability like cmake.

Another customization that needs to be take care of in the case of creating a new project based on this template is the use of cmake-utils. There are 3 options:

• Just copy the files and include them in the new repository.
• Use it as a submodule using the initial URL address.
• Use it as a submodule using a fork of the initial URL address. This allows you to keep the repo separately and have full control on updates and other desired enhancements.

Clarifications on building

The shared object containing the pass is dynamically loaded by opt. This poses a restriction on its build dependency upon opt and its transient dependency to the C++ library it is linked against. So, it is recommended to perform readelf -d $(which opt) and note which implementation of the C++ library it uses (libc++ or libstdc++). Then, you can influence which C++ library your pass uses with the CMAKE_CXX_FLAGS and the -stdlib flag for LLVM.

The main problem stems from the binary incompatibility (ABI) between the two implementations, although they are API compatible since they adhere to the ISO standard. For this reason, libc++ uses the inlined namespace std::__1, which will show up in the errors when you have your pass built against libstdc++ and try to load it using an opt built against libc++.

When LLVM is build with BUILD_SHARED_LIBS=OFF, opt cannot load dynamically any pass built as a shared object, complaining about multiply defined symbols, since it contains everything in its executable. The only workaround is to build your pass in the LLVM tree (resulting in a static archive, also included in the opt executable).

Miscellaneous

When the build script uses LLVM cmake utility functions the lib shared library prefix is omitted.

TODO

• Add travis-ci support.

pedigree's Issues

Upgrade to support latest LLVM release 12

Upgrade to support latest LLVM release 12.

Incorrect generation of control dependences when the block terminator is an unreachable LLVM IR instruction

The LLVM unreachable instructions should not be handled differently, since that may lead to incorrect post-dominance frontier calculation, and therefore an incorrect control dependence graph (CDG).

For example

#include <stdlib.h>
#include <stdio.h>

#define N 5

void foo() {
  int i;
  for (i = 0; i < N; i++) {}
  return;
}

void bar() {
  int i;
  for (i = 0; i < N; i++) {}
  exit(0);
}

The corresponding IR can be produced with clang -emit-llvm -S foo.c -o foo.ll.

The CDG's for both for and bar functions should be identical, but they are not since the bar CDG is empty.

The 2 CFG's only differ by a single unreachable basic block, as can be seen below:

cfg.bar.pdf
cfg.foo.pdf

This issue was triggered by the use case described in 1.

Crash when building the CDGraph of a function with an unreachable block

Hi @compor, sorry to bother you again ;)

When building the CDGraph of the attached foo function (foo.ll.zip), opt crashes with the following error message:

opt: llvm/include/Pedigree/Analysis/PostDominanceFrontier.hpp:116: const pedigree::PostDominanceFrontierBase::DomSetType &pedigree::PostDominanceFrontierBase<llvm::BasicBlock>::calculate(const pedigree::PostDominanceFrontierBase::DomTreeT &) [BlockT = llvm::BasicBlock]: Assertion `blockRoot && "Only one entry block for post domfronts!"' failed.

This issue is probably related to #1 as foo also contains an unreachable block. It is not a regression introduced by #2, LLVM crashes as well before merging it. The problem disappears if I run -unreachableblockelim before. An alternative fix would be to just make all Pedigree passes dependent on this pass.

How to reproduce

1. Assert that running opt -S -pedigree-cdg foo.ll does not yield a crash.

Thanks again!

Use new pass manager

Add infrastructure to use the new pass manager in all passes of this project.