dg llvm-slicer hangs somewhere when slicing sqlite-3.38.0

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

Jun 12 '22 13:06 DemDing

This commit should fix the problem with unsupported instruction: https://github.com/mchalupa/dg/commit/91297431115a8c75ca87e28bedcd386dd46e00ad, 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.

Jun 14 '22 09:06 mchalupa

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

Jun 14 '22 10:06 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.

Jun 15 '22 12:06 DemDing

/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...

Jun 20 '22 11:06 mchalupa

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

Jun 24 '22 12:06 DemDing

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

Jun 29 '22 12:06 mchalupa