sdressler / kerneldataflow

KernelDataFlow

This is an LLVM pass to traverse a "kernel function" (KF) and record its data flow graph. The resulting graph is constructed such that it does not only provides data flows but also a bit of control flow.

Dependencies

• LLVM >= 3.2
• Clang is preferred
• make

Limitations

It is very likely, that this pass does not handle every input. Thus, asserts may happen on various situations. The tool is easily extensible. To add a missing instruction one has to extend src/BlockProcessor/AnalyzeInstruction.cpp.i

Installation

1. Match the settings in Makefile.in to your needs
2. Type make
3. Use the generated KernelDataVolume.so as LLVM pass

Usage

You can input C or C++ code where the kernel function is annotated. Annotation is done by setting __attribute__((annotate("kernel"))) right before the kernel function, i.e. its declaration or definition. Once the kernel function was processed, a graph is generated which currently is written to disk as Graphviz file. This file can then be further processed, e.g. to create a visualization. Furthermore, block-related graphs can be found within the graphs directory. The pass is yet extendable to also use the in-memory graph. To do so, simply create a new folder inside the src directory, copy the Makefile of one of the other sub-directories and adapt it. Also adapt the Makefiles in src and in the root directory as well.

kerneldataflow's Issues

Assertion when graphing -O1-optimized example/loop.c

$ clang -emit-llvm -S -c example/loop.c -o - | opt -O1 -o - | opt -load ./KernelDataFlow.so -KernelDataFlow -o /dev/null && dot -Tpdf graph.dot -o graph.pdf
Found 1 Kernels

; Function Attrs: nounwind uwtable
define void @f(i32* nocapture readonly %in, i32* nocapture %out, i32 %M, i32 %N) #0 {
entry:
%cmp9 = icmp sgt i32 %M, 0
br i1 %cmp9, label %for.cond1.preheader.lr.ph, label %for.end11

for.cond1.preheader.lr.ph: ; preds = %entry
%cmp27 = icmp sgt i32 %N, 0
br label %for.cond1.preheader

for.cond1.preheader: ; preds = %for.inc9, %for.cond1.preheader.lr.ph
%indvars.iv13 = phi i64 [ 0, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next14, %for.inc9 ]
br i1 %cmp27, label %for.body3.lr.ph, label %for.inc9

for.body3.lr.ph: ; preds = %for.cond1.preheader
%arrayidx = getelementptr inbounds i32* %in, i64 %indvars.iv13
br label %for.body3

for.body3: ; preds = %for.body3, %for.body3.lr.ph
%indvars.iv = phi i64 [ 0, %for.body3.lr.ph ], [ %indvars.iv.next, %for.body3 ]
%0 = load i32* %arrayidx, align 4
%arrayidx5 = getelementptr inbounds i32* %in, i64 %indvars.iv
%1 = load i32* %arrayidx5, align 4
%add = add nsw i32 %1, %0
%2 = add nsw i64 %indvars.iv, %indvars.iv13
%arrayidx8 = getelementptr inbounds i32* %out, i64 %2
store i32 %add, i32* %arrayidx8, align 4
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
%lftr.wideiv = trunc i64 %indvars.iv.next to i32
%exitcond = icmp eq i32 %lftr.wideiv, %N
br i1 %exitcond, label %for.inc9, label %for.body3

for.inc9: ; preds = %for.body3, %for.cond1.preheader
%indvars.iv.next14 = add nuw nsw i64 %indvars.iv13, 1
%lftr.wideiv15 = trunc i64 %indvars.iv.next14 to i32
%exitcond16 = icmp eq i32 %lftr.wideiv15, %M
br i1 %exitcond16, label %for.end11, label %for.cond1.preheader

for.end11: ; preds = %for.inc9, %entry
ret void
}

BB processor attached.
Instruction not handled: %lftr.wideiv = trunc i64 %indvars.iv.next to i32
opt: /home/marcusmae/forge/KernelDataFlow/src/BlockProcessor/AnalyzeInstruction.cpp:244: vertexIterator BlockProcessor::analyzeInstruction(llvm::Instruction ): Assertion `0' failed.
0 opt 0x000000000152faa3 llvm::sys::PrintStackTrace(IO_FILE) + 38
1 opt 0x000000000152fd2a
2 opt 0x000000000152f76e
3 libpthread.so.0 0x00007f1f2698bcb0
4 libc.so.6 0x00007f1f259b6425 gsignal + 53
5 libc.so.6 0x00007f1f259b9b8b abort + 379
6 libc.so.6 0x00007f1f259af0ee
7 libc.so.6 0x00007f1f259af192
8 KernelDataFlow.so 0x00007f1f25766b00 BlockProcessor::analyzeInstruction(llvm::Instruction) + 4832
9 KernelDataFlow.so 0x00007f1f25765434 BlockProcessor::analyzeBB(llvm::BasicBlock_) + 100
10 KernelDataFlow.so 0x00007f1f2576d645 BlockProcessor::run() + 373
11 KernelDataFlow.so 0x00007f1f25761536 KernelDataFlow::runOnModule(llvm::Module&) + 358
12 opt 0x00000000014abc8b
13 opt 0x00000000014ac2a0 llvm::legacy::PassManagerImpl::run(llvm::Module&) + 254
14 opt 0x00000000014ac4b3 llvm::legacy::PassManager::run(llvm::Module&) + 39
15 opt 0x0000000000867b14 main + 5778
16 libc.so.6 0x00007f1f259a176d __libc_start_main + 237
17 opt 0x0000000000859799
Stack dump:
0. Program arguments: opt -load ./KernelDataFlow.so -KernelDataFlow -o /dev/null

1. Running pass 'Kernel Data Flow Analysis Pass' on module ''.
   Aborted (core dumped)