# Linear Time Liveness Analysis

DevFeed: [Linear Time Liveness Analysis](<https://devfeed.tech/articles/linear-time-liveness-analysis-25069.md>)

Original publisher: [Read original article](<https://databasearchitects.blogspot.com/2020/04/linear-time-liveness-analysis.html>)

Author: Thomas Neumann (noreply@blogger.com)

Published: 2020-04-28T14:42:00Z

Content type: article

Language: en

Sources: [Database Architects](<https://devfeed.tech/sources/database-architects.md>)

Topics: [Compiler](<https://devfeed.tech/topics/compiler.md>), [Code](<https://devfeed.tech/topics/code.md>), [gcc](<https://devfeed.tech/topics/gcc.md>), [C](<https://devfeed.tech/topics/c.md>)

Tags: [analysis](<https://devfeed.tech/tags/analysis.md>), [c](<https://devfeed.tech/tags/c.md>), [code](<https://devfeed.tech/tags/code.md>), [compilation](<https://devfeed.tech/tags/compilation.md>), [compiler](<https://devfeed.tech/tags/compiler.md>), [compilers](<https://devfeed.tech/tags/compilers.md>), [cpp](<https://devfeed.tech/tags/cpp.md>), [gcc](<https://devfeed.tech/tags/gcc.md>)

## AI overview

The article examines why compilers can take super-linear time on large generated functions with many conditional blocks. It reports that GCC becomes effectively unable to compile sufficiently large examples and that Clang also shows super-linear behavior under optimization. It then introduces a control-flow-graph-based approach to liveness analysis intended to scale better than propagating liveness sets.

## Source excerpt

Standard compiler are usually used with hand-written programs. These programs tend to have reasonably small functions, and can be processed in (nearly) linear time. Generated programs however can be quite large, and compilers sometimes struggle to compile them at all. This can be seen with the following (silly) demonstration script: import subprocess from timeit import default_timer as timer def doTest(size): with open("foo.cpp", "w") as out: print("int foo(int x) {", file=out) for s in range(size): p="x" if s==0 else f'l{s-1}' print (f'int l{s}; if (__builtin_sadd_overflow({p},1,&l{s})) goto error;', file=out) print(f'return l{size-1};error: throw;}}', file=out); start = timer() subprocess.run(["gcc", "-c", "foo.cpp"]) stop = timer() print(size, ": ", (stop-start)) for size in [10,100,1000,10000,100000]: doTest(size) It generates one function with n statements of the form "int lX; if (__builtin_sadd_overflow(lY,1,&lX)) goto error;" which are basically just n additions with overflow checks, and then measures the compile time. The generated code is conceptually a very simple, but it contains a lot of basic blocks due to the large number of ifs. When compiling with gcc we get the following compile times: n101001,00010,000100,000 compilation [s]0.020.040.1934.99> 1h The compile time is dramatically super linear, gcc is basically unable to compile the function if it contains 10,000 ifs or more. In this simple example clang fares better when using -O0, but with -O1 it shows super-linear compile times, too. This is disastrous when processing generated code, where we cannot easily limit the size of individual functions. In our own system we use neither gcc nor clang for query compilation, but we have same problem, namely compiling large generated code. And super-linear runtime quickly becomes an issue when the input is large. One particular important problem in this context is liveness analysis, i.e, figuring out which value is alive at which part of the program. The textb