[analyzer][CrossTU] Lower CTUImportThreshold default value

[gamesh411]

Summary

The default value of 100 makes the analysis slow. Projects of considerable
size can take more time to finish than it is practical. The new default
setting of 8 is based on the analysis of LLVM itself. With the old default
value of 100 the analysis time was over a magnitude slower. Thresholding the
load of ASTUnits is to be extended in the future with a more fine-tuneable
solution that accomodates to the specifics of the project analyzed.

[gamesh411]

update test value

[Szelethus]

Based on discussions I heard in between @dkrupp, @martong and You, this seems appropriate.

[xazax.hun]

The analyzer inlines small functions within a TU regardless of the thresholds. I think it would be sensible to do the same across TUs in the case we don't do this already.

[balazske]

In D82561#2115578, @xazax.hun wrote:

The analyzer inlines small functions within a TU regardless of the thresholds. I think it would be sensible to do the same across TUs in the case we don't do this already.

That means perform a get CTU definition if the TU to be imported (where the function comes from) is small? Otherwise it does not matter how small the function is, it can result in importing of large amount of code. Determining parameters (like "smallness") of the TU is probably not simple.

[gamesh411]

In D82561#2116091, @balazske wrote:

In D82561#2115578, @xazax.hun wrote:

The analyzer inlines small functions within a TU regardless of the thresholds. I think it would be sensible to do the same across TUs in the case we don't do this already.

That means perform a get CTU definition if the TU to be imported (where the function comes from) is small? Otherwise it does not matter how small the function is, it can result in importing of large amount of code. Determining parameters (like "smallness") of the TU is probably not simple.

Measuring the smallness of a function is currently not trivial if the function is in another TU. But theoretically, the creation process of the CTU index has access to the number of declarations in a function, which could be used as a metric for complexity.

Another concern is memory usage. Currently I am working on a solution to approximate the memory usage of declarations by measuring the total memory usage, and the number of declarations inside a TU. Then I can come up with average values for memory used per declaration for projects I test. I could measure multiple projects per language and come up with some statistics that way, but I'm sure that I am not alone with the feeling that there should be a better metric for memory usage other than this roundabout method. All would be well if there were a way to get sizeof(astunit), but I am not aware of any.

[martong]

clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def

324

typo: burder -> burden

[xazax.hun]

In D82561#2116194, @gamesh411 wrote:

In D82561#2116091, @balazske wrote:

That means perform a get CTU definition if the TU to be imported (where the function comes from) is small? Otherwise it does not matter how small the function is, it can result in importing of large amount of code. Determining parameters (like "smallness") of the TU is probably not simple.

Measuring the smallness of a function is currently not trivial if the function is in another TU. But theoretically, the creation process of the CTU index has access to the number of declarations in a function, which could be used as a metric for complexity.

The number of declarations is not a good proxy for complexity.
We talk about 3 calculations here:

1. Loading the TU from disk (which might involve parsing in case the analysis is on demand)
2. Merging the AST sub"trees"
3. Actual inline analysis

1-2 Is cached and the complexity of 2 is largely determined by the number of dependencies in a declaration. I suspect that the number of declarations in a function is not a good estimate of the number of unmerged dependencies (classes and so on).

For 3, we have the CFG node size as a complexity estimate.

The question is how the processing time is split between all these phases.

Another concern is memory usage. Currently I am working on a solution to approximate the memory usage of declarations by measuring the total memory usage, and the number of declarations inside a TU. Then I can come up with average values for memory used per declaration for projects I test. I could measure multiple projects per language and come up with some statistics that way, but I'm sure that I am not alone with the feeling that there should be a better metric for memory usage other than this roundabout method. All would be well if there were a way to get sizeof(astunit), but I am not aware of any.

Yeah, loading a big TU into the memory just for a single small function might not be the best to do. However, when we dramatically reducing the CTU threshold, the analysis will be more unstable in the sense that adding a new function call will change the order in which we analyze functions. That will change the order of CTU imports. That will change the set of TUs that will be imported. It might not be a problem as the analyzer already can exhibit this behavior: a small code change can make unrelated diagnostics appear or disappear. But a small CTU threshold will likely make this phenomenon worse.

Just to be clear I am on board with this patch, I was merely brainstorming for future improvements :)

clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def

 
 //===----------------------------------------------------------------------===//
 // Unsigned analyzer options.
 //===----------------------------------------------------------------------===//
 
 ANALYZER_OPTION(unsigned, CTUImportThreshold, "ctu-import-threshold",
                 "The maximal amount of translation units that is considered "
                 "for import when inlining functions during CTU analysis. "
                 "Lowering this threshold can alleviate the memory burder of "
                 "analysis with many interdependent definitions located in "
                 "various translation units.",
-                100u)
+                8u)
 
 ANALYZER_OPTION(
     unsigned, AlwaysInlineSize, "ipa-always-inline-size",
     "The size of the functions (in basic blocks), which should be considered "
     "to be small enough to always inline.",
     3)
 
 ANALYZER_OPTION(

clang/test/Analysis/analyzer-config.c

 // CHECK-NEXT: core.CallAndMessage:CXXThisMethodCall = true
 // CHECK-NEXT: core.CallAndMessage:FunctionPointer = true
 // CHECK-NEXT: core.CallAndMessage:NilReceiver = true
 // CHECK-NEXT: core.CallAndMessage:ParameterCount = true
 // CHECK-NEXT: core.CallAndMessage:UndefReceiver = true
 // CHECK-NEXT: cplusplus.Move:WarnOn = KnownsAndLocals
 // CHECK-NEXT: crosscheck-with-z3 = false
 // CHECK-NEXT: ctu-dir = ""
-// CHECK-NEXT: ctu-import-threshold = 100
+// CHECK-NEXT: ctu-import-threshold = 8
 // CHECK-NEXT: ctu-index-name = externalDefMap.txt
 // CHECK-NEXT: ctu-invocation-list = invocations.yaml
 // CHECK-NEXT: deadcode.DeadStores:ShowFixIts = false
 // CHECK-NEXT: deadcode.DeadStores:WarnForDeadNestedAssignments = true
 // CHECK-NEXT: debug.AnalysisOrder:* = false
 // CHECK-NEXT: debug.AnalysisOrder:Bind = false
 // CHECK-NEXT: debug.AnalysisOrder:EndAnalysis = false
 // CHECK-NEXT: debug.AnalysisOrder:EndFunction = false