llvm-slicer hangs somewhere when slicing sqlite-3.38.0

[DemDing]

Hi, llvm-slicer hung when I tried to do backward slice on sqlite-3.38.0 with following command:

./llvm-slicer --cutoff-diverging=false -sc='fsync' -entry=sqlite3_step sqlite3.bc

The output of llvm-slicer is :

IntToPtr with constant: = inttoptr i64 1 to i8*
IntToPtr with constant: = inttoptr i64 3 to i8*
IntToPtr with constant: = inttoptr i64 2 to i8*
IntToPtr with constant: = inttoptr i64 4 to i8*
IntToPtr with constant: = inttoptr i64 99 to i8*
IntToPtr with constant: = inttoptr i64 6 to i8*
IntToPtr with constant: = inttoptr i64 5 to i8*
WARNING: Non-0 memset: call void @llvm.memset.p0i8.i64(i8* align 1 %54, i8 -86, i64 128, i1 false), !dbg !7142
WARNING: Non-0 memset: call void @llvm.memset.p0i8.i64(i8* align 1 %77, i8 -86, i64 %82, i1 false), !dbg !7173
WARNING: Non-0 memset: call void @llvm.memset.p0i8.i64(i8* align 8 %104, i8 -1, i64 16, i1 false), !dbg !7180
fence seq_cst, !dbg !7092
WARNING: Non-0 memset: call void @llvm.memset.p0i8.i64(i8* align 1 %565, i8 1, i64 %568, i1 false), !dbg !7641
WARNING: Non-0 memset: call void @llvm.memset.p0i8.i64(i8* align 1 %275, i8 1, i64 %278, i1 false), !dbg !7405
WARNING: Non-0 memset: call void @llvm.memset.p0i8.i64(i8* align 1 %816, i8 1, i64 %819, i1 false), !dbg !7872
IntToPtr with constant: = inttoptr i64 -1 to i8*
IntToPtr with constant: = inttoptr i64 -1 to void (i8*)*

After printing the message above, llvm-slicer hung and didn't print any message anymore.

I also tried to compile dg with debug flag and sanitizer command DCMAKE_BUILD_TYPE=Debug -DUSE_SANITIZERS=ON , and then I got assertion failure:

IntToPtr with constant: = inttoptr i64 1 to i8*
IntToPtr with constant: = inttoptr i64 3 to i8*
IntToPtr with constant: = inttoptr i64 2 to i8*
IntToPtr with constant: = inttoptr i64 4 to i8*
IntToPtr with constant: = inttoptr i64 99 to i8*
IntToPtr with constant: = inttoptr i64 6 to i8*
IntToPtr with constant: = inttoptr i64 5 to i8*
WARNING: Non-0 memset: call void @llvm.memset.p0i8.i64(i8* align 1 %54, i8 -86, i64 128, i1 false), !dbg !7142
WARNING: Non-0 memset: call void @llvm.memset.p0i8.i64(i8* align 1 %77, i8 -86, i64 %82, i1 false), !dbg !7173
WARNING: Non-0 memset: call void @llvm.memset.p0i8.i64(i8* align 8 %104, i8 -1, i64 16, i1 false), !dbg !7180
fence seq_cst, !dbg !7092
llvm-slicer: /root/dg/lib/llvm/PointerAnalysis/PointerGraph.cpp:415: dg::pta::LLVMPointerGraphBuilder::PSNodesSeq& dg::pta::LLVMPointerGraphBuilder::buildInstruction(const llvm::Instruction&): Assertion `0 && "Unhandled instruction"' failed.
Aborted

I use gllvm to produce the bitcode file of sqlite3, and the running environment is as follows:

ubuntu 20.04
clang-10

Could you please tell me how to solve it? The bitcode file is attached below.
sqlite3_bitcode.zip

[mchalupa]

This commit should fix the problem with unsupported instruction: 9129743, but that is not probably the problem that makes DG hang. As far as I can tell, DG does not hang, the pointer analysis just takes too long. You can try to use --pta-field-sensitive=0 to speed up the analysis.

[DemDing]

Thanks a lot! I'll try for this update right away and let you know the result.

[DemDing]

Hi, I've tried the branch skip-fence dg, but unfortunately, I had segment fault error using the command ./llvm-slicer --pta-field-sensitive=0 -cutoff-diverging=false -sc 'fsync' -entry=sqlite3_step sqlite3.bc:

IntToPtr with constant: = inttoptr i64 1 to i8*
IntToPtr with constant: = inttoptr i64 2 to i8*
IntToPtr with constant: = inttoptr i64 4 to i8*
IntToPtr with constant: = inttoptr i64 3 to i8*
IntToPtr with constant: = inttoptr i64 99 to i8*
IntToPtr with constant: = inttoptr i64 5 to i8*
/usr/lib/llvm-10/lib/libLLVM-10.so.1(_ZN4llvm3sys15PrintStackTraceERNS_11raw_ostreamE+0x1f)[0x7f880679f4ff]
/usr/lib/llvm-10/lib/libLLVM-10.so.1(_ZN4llvm3sys17RunSignalHandlersEv+0x22)[0x7f880679d782]
/usr/lib/llvm-10/lib/libLLVM-10.so.1(+0x981ac5)[0x7f880679fac5]
/lib/x86_64-linux-gnu/libc.so.6(+0x43090)[0x7f8805a88090]
/root/dg-skip-fence/bd/lib/libdgllvmpta.so(_ZN2dg3pta23LLVMPointerGraphBuilder19createInsertElementEPKN4llvm11InstructionE+0x27c)[0x7f880a4f0a6c]
/root/dg-skip-fence/bd/lib/libdgllvmpta.so(_ZN2dg3pta23LLVMPointerGraphBuilder22buildPointerGraphBlockERKN4llvm10BasicBlockEPNS0_15PointerSubgraphE+0x96)[0x7f880a 4e4c76]
/root/dg-skip-fence/bd/lib/libdgllvmpta.so(_ZN2dg3pta23LLVMPointerGraphBuilder13buildFunctionERKN4llvm8FunctionE+0x416)[0x7f880a4ded86]
/root/dg-skip-fence/bd/lib/libdgllvmpta.so(_ZN2dg3pta23LLVMPointerGraphBuilder19createOrGetSubgraphEPKN4llvm8FunctionE+0x8b)[0x7f880a4df21b]
/root/dg-skip-fence/bd/lib/libdgllvmpta.so(_ZN2dg3pta23LLVMPointerGraphBuilder21getAndConnectSubgraphEPKN4llvm8FunctionEPKNS2_8CallInstEPNS0_6PSNodeE+0x36)[0x7f88 0a4e0276]
/root/dg-skip-fence/bd/lib/libdgllvmpta.so(_ZN2dg3pta23LLVMPointerGraphBuilder20createCallToFunctionEPKN4llvm8CallInstEPKNS2_8FunctionE+0x1ab)[0x7f880a4e0a0b]
/root/dg-skip-fence/bd/lib/libdgllvmpta.so(_ZN2dg3pta23LLVMPointerGraphBuilder10createCallEPKN4llvm11InstructionE+0x65)[0x7f880a4f5ea5]
/root/dg-skip-fence/bd/lib/libdgllvmpta.so(_ZN2dg3pta23LLVMPointerGraphBuilder22buildPointerGraphBlockERKN4llvm10BasicBlockEPNS0_15PointerSubgraphE+0x96)[0x7f880a 4e4c76]
/root/dg-skip-fence/bd/lib/libdgllvmpta.so(_ZN2dg3pta23LLVMPointerGraphBuilder13buildFunctionERKN4llvm8FunctionE+0x416)[0x7f880a4ded86]
/root/dg-skip-fence/bd/lib/libdgllvmpta.so(_ZN2dg3pta23LLVMPointerGraphBuilder19createOrGetSubgraphEPKN4llvm8FunctionE+0x8b)[0x7f880a4df21b]
/root/dg-skip-fence/bd/lib/libdgllvmpta.so(_ZN2dg3pta23LLVMPointerGraphBuilder21getAndConnectSubgraphEPKN4llvm8FunctionEPKNS2_8CallInstEPNS0_6PSNodeE+0x36)[0x7f88 0a4e0276]
/root/dg-skip-fence/bd/lib/libdgllvmpta.so(_ZN2dg3pta23LLVMPointerGraphBuilder20createCallToFunctionEPKN4llvm8CallInstEPKNS2_8FunctionE+0x1ab)[0x7f880a4e0a0b]
/root/dg-skip-fence/bd/lib/libdgllvmpta.so(_ZN2dg3pta23LLVMPointerGraphBuilder10createCallEPKN4llvm11InstructionE+0x65)[0x7f880a4f5ea5]
/root/dg-skip-fence/bd/lib/libdgllvmpta.so(_ZN2dg3pta23LLVMPointerGraphBuilder22buildPointerGraphBlockERKN4llvm10BasicBlockEPNS0_15PointerSubgraphE+0x96)[0x7f880a 4e4c76]
/root/dg-skip-fence/bd/lib/libdgllvmpta.so(_ZN2dg3pta23LLVMPointerGraphBuilder13buildFunctionERKN4llvm8FunctionE+0x416)[0x7f880a4ded86]
/root/dg-skip-fence/bd/lib/libdgllvmpta.so(_ZN2dg3pta23LLVMPointerGraphBuilder21buildLLVMPointerGraphEv+0x5a)[0x7f880a4dffda]
./llvm-slicer(_ZN2dg21DGLLVMPointerAnalysis10initializeEv+0x44)[0x560520071db4]
./llvm-slicer(_ZN6Slicer7buildDGEb+0x168)[0x560520072d08]
./llvm-slicer(main+0x32c)[0x560520062eec]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf3)[0x7f8805a69083]
./llvm-slicer(_start+0x2e)[0x56052006393e]
Segmentation fault (core dumped)

When running in debug mode of dg, the output is:

IntToPtr with constant: = inttoptr i64 1 to i8*
IntToPtr with constant: = inttoptr i64 2 to i8*
IntToPtr with constant: = inttoptr i64 4 to i8*
IntToPtr with constant: = inttoptr i64 3 to i8*
IntToPtr with constant: = inttoptr i64 99 to i8*
IntToPtr with constant: = inttoptr i64 5 to i8*
/root/dg-skip-fence/include/dg/SubgraphNode.h:152:9: runtime error: member access within null pointer of type 'struct PSNode'

The above tests were run in the environment where sqlite3 is compiled without any compile options. However, when I compiled sqlite3 with the command: CC=gclang CFALGS='-g -O0 -DSQLITE_DEBUG' ./configure and produced sqlite3_debug.bc file to run backward slice in the cloud environment for 24 hours, the same problem as before that dg produced no message happened:

IntToPtr with constant: = inttoptr i64 1 to i8*
IntToPtr with constant: = inttoptr i64 3 to i8*
IntToPtr with constant: = inttoptr i64 2 to i8*
IntToPtr with constant: = inttoptr i64 4 to i8*
IntToPtr with constant: = inttoptr i64 99 to i8*
IntToPtr with constant: = inttoptr i64 5 to i8*
WARNING: Non-0 memset: call void @llvm.memset.p0i8.i64(i8* align 1 %54, i8 -86, i64 128, i1 false), !dbg !7078
WARNING: Non-0 memset: call void @llvm.memset.p0i8.i64(i8* align 1 %77, i8 -86, i64 %82, i1 false), !dbg !7109
WARNING: Non-0 memset: call void @llvm.memset.p0i8.i64(i8* align 8 %104, i8 -1, i64 16, i1 false), !dbg !7116
WARNING: Non-0 memset: call void @llvm.memset.p0i8.i64(i8* align 1 %565, i8 1, i64 %568, i1 false), !dbg !7577
WARNING: Non-0 memset: call void @llvm.memset.p0i8.i64(i8* align 1 %275, i8 1, i64 %278, i1 false), !dbg !7341
WARNING: Non-0 memset: call void @llvm.memset.p0i8.i64(i8* align 1 %816, i8 1, i64 %819, i1 false), !dbg !7808
IntToPtr with constant: = inttoptr i64 -1 to i8*
IntToPtr with constant: = inttoptr i64 -1 to void (i8*)*

Besides, when I set -cutoff-diverging=true, the output information is indeed more than the previous version before the commit 9129743.

Could you please tell me how to solve it?
Thanks.

[mchalupa]

/root/dg-skip-fence/include/dg/SubgraphNode.h:152:9: runtime error: member access within null pointer of type 'struct PSNode'

How long does it take before the crash? I cannot reproduce that.

Besides, when I set -cutoff-diverging=true, the output information is indeed more than the previous version before the commit 9129743.

I optimized that part a bit.

the cloud environment for 24 hours, the same problem as before that dg produced no message happened:

The PTA analysis seems to be too inefficient to analyse this piece of code. cutoff-diverging could help if it matches few enough instructions as criteria. However, I see that the slicing criterion is fsync which is matched to over 200000 instructions. If fsync should be a call, use fsync() to filter out only calls of fsync. Nvertheless, I do not see any call of fsync in the bitcode...

[DemDing]

How long does it take before the crash? I cannot reproduce that.

dg crashes as soon as it starts running and the crashed bitcode file is attached below.
sqlite3_crash.zip

[mchalupa]

You can try the commit above that should fix the crash. The runtime will, however, not change...