Question on LiveVariables analysis

Hi,

While LiveVariables analysis (tools/clang/lib/Analysis/LiveVariables.cpp) does not generate any output? Specifically, for this simple program:

1 int main(int argc, char *argv[])
2 {
3 int a,b,c,d,x;
4
5 a = 3; //Basic block B1
6 b = 5;
7 d = 4;
8 x = 100;
9
10 if(a>b){ //Basic block B2
11 c = a+b;
12 d = 2;
13 }
14
15 c = 4; //Basic block B3
16 return b * d + c;
17 }

This simple example is taken from this wiki page illustrating live variables analysis (http://en.wikipedia.org/wiki/Live_variable_analysis).
Both B2 and B3 should have live variables, but the output (using LiveVariables::dumpBlockLiveness(SourceManager &)) says no live variables exist. I am trying to use this analysis as an example on how to write a good analysis algorithm for Clang, but really did not expect this behavior for this analysis.
Anybody who knows the answer please let me know. Many thanks!!!

This is what I am seeing:

$ clang -cc1 -analyze -analyzer-checker=debug.DumpLiveVars t.c

[ B0 (live variables at block exit) ]

[ B1 (live variables at block exit) ]

[ B2 (live variables at block exit) ]
b t.c:2:10
d t.c:2:16

[ B3 (live variables at block exit) ]
a t.c:2:7
b t.c:2:10
d t.c:2:16

[ B4 (live variables at block exit) ]

I also think the number of the blocks is not quite right in your example, or at least how they correspond to Clang’s CFG:

$ clang -cc1 -analyze -analyzer-checker=debug.DumpCFG t.c

[ B4 (ENTRY) ]
Predecessors (0):
Successors (1): B3

[ B1 ]
1: 4
2: c
3: [B1.2] = [B1.1]
4: b
5: [B1.4]
6: d
7: [B1.6]
8: [B1.5] * [B1.7]
9: c
10: [B1.9]
11: [B1.8] + [B1.10]
12: return [B1.11];
Predecessors (2): B2 B3
Successors (1): B0

[ B2 ]
1: a
2: [B2.1]
3: b
4: [B2.3]
5: [B2.2] + [B2.4]
6: c
7: [B2.6] = [B2.5]
8: 2
9: d
10: [B2.9] = [B2.8]
Predecessors (1): B3
Successors (1): B1

[ B3 ]
1: int a;
2: int b;
3: int c;
4: int d;
5: int x;
6: 3
7: a
8: [B3.7] = [B3.6]
9: 5
10: b
11: [B3.10] = [B3.9]
12: 4
13: d
14: [B3.13] = [B3.12]
15: 100
16: x
17: [B3.16] = [B3.15]
18: a
19: [B3.18]
20: b
21: [B3.20]
22: [B3.19] > [B3.21]
T: if [B3.22]
Predecessors (1): B4
Successors (2): B2 B1

[ B0 (EXIT) ]
Predecessors (1): B1
Successors (0):

Block B3 is actually the entrance block, since the CFG is built bottom-up.

Perhaps there is something not quite right with how you are running the checkers?

Hi, Ted

I will be very curious why results in your environment are correct. Attached is my test code. I stepped into the program using GDB, it turned out that no live variables can be found. Take the last return statement in my previous example program as an example: return b * d + c. The transfer function eventually called the default StmtVisit function which did not recognize variables b, d, c which are actually used.The only function in LiveVariables.cpp that can generate live variables is VisitDeclRefExpr(), but when running the program this function is never called.

I am using the newest version of Clang/LLVM. Is it because my environment setup is wrong?

main.cpp (2.86 KB)

On my testing environment, the UninitializedValues.cpp has the same problem (do not have any output). Both analyses are based on the StmtVisitor interface. I think there may be a version mismatch, that is these two analyses are based on an older version of StmtVisitor class to work? I just downloaded a new version from website and did all tests again and still have this problem.

Also, it seems there is an assert error in UninitializedValues.cpp. Giving this test program:

1 int main(int argc, char *argv[])
2 {
3 int x=3, y = 5, z = 6;
4
5 if(x<0) {
6 while(y>0){
7 y–;
8 x = z+1;
9 }
10 }else x = y;
11 return 0;
12 }
Here is the assert error:

Assertion failed: (res.getDeclRefExpr() == lastDR), function VisitUnaryOperator, file /Users/gplong/llvm/tools/clang/lib/Analysis/UninitializedValues.cpp, line 529.

This message is triggered in call VisitUnaryOperator(). The line number may not be correct because I added some print statements.

Hi Guoping,

I cannot reproduce the assertion failure.

Is it still reproducible with the latest revision of Clang/LLVM? If yes, can you send the command line you used.

Thanks,
Anna.

Hi, Anna

Here are steps on how I got this error:
1 Get the latest code:
A. svn co http://llvm.org/svn/llvm-project/llvm/trunk llvm
B. svn co http://llvm.org/svn/llvm-project/cfe/trunk clang
2. Configure & Make
A. make a separate directory for build: makedir llvm-build
B. In llvm-build/, using cmake to generate the Makefile:
cmake …/llvm -DCMAKE_BUILD_TYPE=Debug
C. make & make install
3. Add a test:
A. create a directory: tools/clang/examples/Debug
B. write a test file, as attached.
C. Modify tools/clang/CMakeLists.txt to build the examples/ directory.
D. Add CMakeLists.txt in tools/clang/examples/Debug to build the newly added test program.
E. when the program is built, run it with the previous test program to get this error.

I am using MacOS 10.6.8, x86-64 Intel platform.
It seems my source tree is not in the right configuration? Please let me know what’s wrong in my environment. I will be deeply appreciated. Thanks.

main.cpp (3.14 KB)

Hi Guoping,

I thought that you saw an assertion failure by running $ clang --analyze. I did not realize that you are running custom code to build up the UninitializedVariables. I am not familiar enough with that code to know what’s wrong without debugging it.

Most likely there is some issue with the way you build the analysis in your code; you should probably look at other uses of UninitializedVariables to see what you are missing. Also, try to find out at which step the first symptoms of the problem occur - for example, do you get a CFG different from what you see when dumping the CFG with a debug checker? (See the command from Ted’s reply below.)

I noticed that you do not pass CFGBuildOptions when constructing the AnalysisContext. Here is some code from AnalysisBasedWarnings.cpp, which implies that you might need to request linearized CFG.

// Unreachable code analysis requires a linearized CFG.
AC.getCFGBuildOptions().setAllAlwaysAdd();

Also, what are you trying to do? Maybe just writing a checker would be a simpler solution.

Hope this helps,
Anna.

You need to do B within the ‘tools’ subdirectory of A.

Specifically:

$ svn co http://llvm.org/svn/llvm-project/llvm/trunk llvm
$ cd llvm/tools
$ svn co http://llvm.org/svn/llvm-project/cfe/trunk clang

Thank you! That just made my day!

Can anybody elaborate or give a pointer on what is meant by
a linearized CFG in this case?
I found this paper [1] which contains some info on CFG linearization.

Which algorithm is implemented for LiveVariables and CFG linearization
in clang static analyzer? Any pointers?

Regards,
Georg

[1]
paper: http://compilers.cs.uni-saarland.de/papers/karrenberg_opencl.pdf
DOI paper: http://dx.doi.org/10.1007/978-3-642-28652-0_1
slides: http://llvm.org/devmtg/2012-04-12/Slides/Ralf_Karrenberg.pdf

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Most likely there is some issue with the way you build the analysis
in your code; you should probably look at other uses of
UninitializedVariables to see what you are missing. Also, try to
find out at which step the first symptoms of the problem occur -
for example, do you get a CFG different from what you see when
dumping the CFG with a debug checker? (See the command from Ted's
reply below.)

I noticed that you do not pass CFGBuildOptions when constructing
the AnalysisContext. Here is some code from
AnalysisBasedWarnings.cpp, which implies that you might need to
request linearized CFG. // Unreachable code analysis requires a
linearized CFG. AC.getCFGBuildOptions().setAllAlwaysAdd();

Thank you! That just made my day!

Can anybody elaborate or give a pointer on what is meant by
a linearized CFG in this case?

It does not refer to an existing term. Linearized CFG is the mode where each AST subexpression is represented as an element in the basic block (instead of elements being expressions, which is how CFG was originally implemented).

(We should consider having this on by default!)