<commit_before># DependenceGraph
DependenceGraph is a library which implementats dependence graph for programs.
It contains set of generic templates that can be specialized to user's needs.
DependenceGraph can be used for different analyses, optimizations or program slicing.

Whole project is under hard developement and lacks documentation for now,
so in the case of need, contact us by an e-mail (below).

## LLVM DependenceGraph && llvm-slicer

We have implemented dependence graph for LLVM and a static slicer for LLVM.

### Requirements & Compilation

LLVM DependenceGraph needs LLVM 3.4. Currently, the branch being developed is backport-llvm-3.4,
so checkout the project like this:

```
git clone https://github.com/mchalupa/dg -b backport-llvm-3.4
cd dg
```

One you have the project cloned, you need to configure it.
Fully manual configuration would look like this:

```
LLVM_DIR=path/to/llvm/share/llvm/cmake cmake -DLLVM_SRC_PATH=/path/to/src -DLLVM_BUILD_PATH=/path/to/build .
```

LLVM\_DIR is environment variable used by LLVM to find cmake config files
(it points to the build or install directory),
LLVM\_SRC\_DIR is variable that tells cmake where to look for llvm's sources
and it is used to override include paths. The same holds for LLVM\_BUILD\_PATH
that is used for overriding library paths. Usually, you don't need to specify
all these variables. When LLVM 3.4 is installed on your system in standard paths
(and no other LLVM is installed), the configuration should look just like:

```
cmake .
```

If there is any collision (i. e. more versions of LLVM installed),
you may need to define LLVM\_DIR variable to point to the directory where
config files of the installed version are ($PREFIX/share/llvm/cmake).
If you have LLVM compiled from sources, but not installed anywhere,
you may need to use LLVM\_SRC\_PATH and LLVM\_BUILD\_PATH variables too.
For the last case, suppose you have LLVM built in /home/user/llvm-build from
sources in /home/user/llvm-src. Then following configuration should work:

```
LLVM_DIR=/home/user/llvm-build/share/llvm/cmake cmake -DLLVM_SRC_PATH=/home/user/llvm-src -DLLVM_BUILD_PATH=/home/user/llvm-build .
```

After configuring the project, usual make takes place:

```
make -j4
```

### Using the slicer

Compiled slicer can be found in the tools subdirectory. First, you need to compile your
program into LLVM (make sure you are using the LLVM 3.4 version binaries!):

```
clang -c -emit-llvm source.c -o bytecode.bc
```

If the program is split into more programs (exactly one of them must contain main),
you must compile all of them separately (as above) and then link the bytecodes using llvm-link:

```
llvm-link bytecode1.bc bytecode2.bc ... -o bytecode.bc
```

Now you're ready to slice the program:

```
./llvm-slicer -c slicing_criterion bytecode.bc
```

The slicing\_criterion is a call-site of some function or 'ret' when slicing
with respect to return value of the main function.

To export dependence graph to .dot file, use:

```
./llvm-dg-dump bytecode.bc > file.dot
```

You can highligh nodes from dependence graph that will be in the slice using -mark switch:

```
./llvm-dg-dump -mark slicing_criterion bytecode.bc > file.dot
```

In the tools/ directory, there are few scripts for convenient manipulation
with the sliced bytecode. First is sliced-diff.sh. This script takes file and shows
differences after slicing. It uses meld or kompare or just diff program
to display the results (the first that is available on the system, in this order)

```
./llvm-slicer -c crit code.bc
./slicer-diff.sh code.bc
```

The other is wrapper around llvm-dg-dump. It uses evince or okular (or xdg-open).
It takes exactly the same arguments as llvm-dg-dump:

```
./ldg-show.sh -mark crit code.bc
```

### Example

We can try slice for example this program (with respect to the assertion):

```C
#include <assert.h>
#include <stdio.h><commit_msg>README: add note about -debug option<commit_after># DependenceGraph
DependenceGraph is a library which implementats dependence graph for programs.
It contains set of generic templates that can be specialized to user's needs.
DependenceGraph can be used for different analyses, optimizations or program slicing.

Whole project is under hard developement and lacks documentation for now,
so in the case of need, contact us by an e-mail (below).

## LLVM DependenceGraph && llvm-slicer

We have implemented dependence graph for LLVM and a static slicer for LLVM.

### Requirements & Compilation

LLVM DependenceGraph needs LLVM 3.4. Currently, the branch being developed is backport-llvm-3.4,
so checkout the project like this:

```
git clone https://github.com/mchalupa/dg -b backport-llvm-3.4
cd dg
```

One you have the project cloned, you need to configure it.
Fully manual configuration would look like this:

```
LLVM_DIR=path/to/llvm/share/llvm/cmake cmake -DLLVM_SRC_PATH=/path/to/src -DLLVM_BUILD_PATH=/path/to/build .
```

LLVM\_DIR is environment variable used by LLVM to find cmake config files
(it points to the build or install directory),
LLVM\_SRC\_DIR is variable that tells cmake where to look for llvm's sources
and it is used to override include paths. The same holds for LLVM\_BUILD\_PATH
that is used for overriding library paths. Usually, you don't need to specify
all these variables. When LLVM 3.4 is installed on your system in standard paths
(and no other LLVM is installed), the configuration should look just like:

```
cmake .
```

If there is any collision (i. e. more versions of LLVM installed),
you may need to define LLVM\_DIR variable to point to the directory where
config files of the installed version are ($PREFIX/share/llvm/cmake).
If you have LLVM compiled from sources, but not installed anywhere,
you may need to use LLVM\_SRC\_PATH and LLVM\_BUILD\_PATH variables too.
For the last case, suppose you have LLVM built in /home/user/llvm-build from
sources in /home/user/llvm-src. Then following configuration should work:

```
LLVM_DIR=/home/user/llvm-build/share/llvm/cmake cmake -DLLVM_SRC_PATH=/home/user/llvm-src -DLLVM_BUILD_PATH=/home/user/llvm-build .
```

After configuring the project, usual make takes place:

```
make -j4
```

### Using the slicer

Compiled slicer can be found in the tools subdirectory. First, you need to compile your
program into LLVM (make sure you are using the LLVM 3.4 version binaries!):

```
clang -c -emit-llvm source.c -o bytecode.bc
```

If the program is split into more programs (exactly one of them must contain main),
you must compile all of them separately (as above) and then link the bytecodes using llvm-link:

```
llvm-link bytecode1.bc bytecode2.bc ... -o bytecode.bc
```

Now you're ready to slice the program:

```
./llvm-slicer -c slicing_criterion bytecode.bc
```

The slicing\_criterion is a call-site of some function or 'ret' when slicing
with respect to return value of the main function.

To export dependence graph to .dot file, use:

```
./llvm-dg-dump bytecode.bc > file.dot
```

You can highligh nodes from dependence graph that will be in the slice using -mark switch:

```
./llvm-dg-dump -mark slicing_criterion bytecode.bc > file.dot
```

In the tools/ directory, there are few scripts for convenient manipulation
with the sliced bytecode. First is sliced-diff.sh. This script takes file and shows
differences after slicing. It uses meld or kompare or just diff program
to display the results (the first that is available on the system, in this order)

```
./llvm-slicer -c crit code.bc
./slicer-diff.sh code.bc
```

The other is wrapper around llvm-dg-dump. It uses evince or okular (or xdg-open).
It takes exactly the same arguments as llvm-dg-dump:

```
./ldg-show.sh -mark crit code.bc
```
If the dependence graph is too big to be displayed using .dot files, you can debug the slice right from
the LLVM. Just pass -debug option to llvm-slicer and it will store readable annotated LLVM in file-debug.ll
(where file.bc is the name of file being sliced). There are more options (llvm-slicer -help for all of them),
but the most interesting is probably -debug slicer:

```
./llvm-slicer -c crit -debug slicer code.bc
```

The content of code-debug.ll will look like this:
```LLVM
; <label>:25                                      ; preds = %20
  ; x   call void @llvm.dbg.value(metadata !{i32* %i}, i64 0, metadata !151), !dbg !164
  %26 = load i32* %i, align 4, !dbg !164
  %27 = add nsw i32 %26, 1, !dbg !164
  ; x   call void @llvm.dbg.value(metadata !{i32 %27}, i64 0, metadata !151), !dbg !164
  store i32 %27, i32* %i, align 4, !dbg !164
  ; x   call void @llvm.dbg.value(metadata !{i32* %j}, i64 0, metadata !153), !dbg !161
  ; x   %28 = load i32* %j, align 4, !dbg !161
  ; x   %29 = add nsw i32 %28, 1, !dbg !161
  ; x   call void @llvm.dbg.value(metadata !{i32 %29}, i64 0, metadata !153), !dbg !161
  ; x   br label %20, !dbg !165

.critedge:                                        ; preds = %20
  ; x   call void @llvm.dbg.value(metadata !{i32* %j}, i64 0, metadata !153), !dbg !166
  ; x   %30 = load i32* %j, align 4, !dbg !166
  ; x   %31 = icmp sgt i32 %30, 99, !dbg !166
  ; x   br i1 %31, label %19, label %32, !dbg !166
```

Other interesting debugging options are ptr, dd, cd, postdom to annotate points-to information,
data dependences, control dependences or post-dominator information. You can chain few -debug options (-debug cd -debug slice)

### Example

We can try slice for example this program (with respect to the assertion):

```C
#include <assert.h>
#include <stdio.h>
{'fraction_non_alphanumeric': 0.0916255122412525, 'fraction_numerical': 0.01796784701061259, 'mean_word_length': 3.831472081218274, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 12, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1606263', 'n_tokens_mistral': 3065, 'n_tokens_neox': 2843, 'n_words': 1326}