[analyzer] Add StackSizeChecker to StaticAnalyzer

[mate1214]

Summary

This checker can be used to warn about potential stack overflows or be used to estimate the size of used stack space. Both Clang Static Analyzer and Clang-Tidy versions exist.

The Clang-Tidy version references the StackUsageMeasuringVisitor class included in this commit so it can only come after this.

Both versions work by examining function bodies via the AST:

• the static analyzer version can follow and summarize the space used by call chains
• while the Tidy one version can analyze function bodies faster, one by one.

This version emits warnings if the estimated stack size surpasses the StackUsageLimit parameter, which is measured in bytes and defaults to 100 000. Setting it to some small value can be used to turn the checker into a statistical tool since the calculated values are included in the warning messages.

The calculations used for the size estimations do not take into account potential compile-time optimizations and contain some
minor simplifications. Only the information stored in the AST is used and variable lifetime rules are respected. The calculations in a particular function body are carried out by the StackUsageMeasuringVisitor class, which gives a composite result about a piece of the AST containing the maximal estimated space, the space that remain in use after the execution of those lines and flags about encountered variable length arrays or special nodes that satisfy a given predicate (e.g.: templates).

The current version takes no special actions upon encountering variable length arrays, the Tidy version has a simple extra logic
for them. The tests are divided between the two versions, the static analyzer ones are about the ability to calculate the size
of a complete call stack and the Tidy ones focus on particular statements and expression types, this is referenced
in one of the comments of the test files for those who want to use the test cases to understand the checker a little bit more.

The code favors readability and maintainability over performance in some places.

[Szelethus]

Hi!

Always great to see a new checker! I've started working in this project little over half a year ago, so I don't claim to be an expert, read my remarks as such! It'll be some time before I go through the entire code, but so far here are the things that caught my eye.

I think you should move the checker related files to a new folder, maybe StackOverflow/?

include/clang/StaticAnalyzer/Checkers/Checkers.td

143–146

Alphabetical sorting?
(get it? alphabetical? I'm sorry.)

include/clang/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.h

16

Missing header guard.

25

You included map but I don't see std::map anywhere?

28

Use ento after clang. Btw, does anybody know what ento refers to? Never got to know it :D

namespace clang {
namespace ento {
namespace stack {

57–60

Since this is the only constructor of this visitor, I think C++11 in-class member initialization would be nicer.

62

It isn't obvious to me what this function does.

64

travel

94

Are you sure this function belongs in a visitor?

143–144

// end of namespace .*

lib/StaticAnalyzer/Checkers/StackSizeChecker.cpp

19

I bet you can't just #include this without getting some nasty buildbut errors down the line, just #include "StackUsageMeasuringVisitor.h".

25

Don't include standard stream libraries: https://llvm.org/docs/CodingStandards.html#include-iostream-is-forbidden

34

If you have a conversion operator to int, do you need operator==?

41

I think you don't need to make this mutable anymore, you can just initialize it in the constructor.

68–77

size_t length(const llvm::ImmutableList<StackInt> &L) {
  int Length = 0;
  for (auto It = L.begin(), E = L.end(); It != E; ++It)
    ++Length;
  return Length;
}

78

// end of anonymous namespace

80

Would look better right below the definition of StackInt.

81

I think some dividers would help a lot:

//===----------------------------------------------------------------------===//
// Methods for StackSizeChecker.
//===----------------------------------------------------------------------===//

94

Use LLVM streams.

llvm::SmallString<20> WarningBuf;
llvm::raw_svector_ostream OS(WarningBuf);
OS << "whatever"<< " needs" << " to" << " be" << " concatenated";

104

It isn't obvious to me why what "StackLevels" mean. Did you mean depth?

107–113

You use dyn_cast_or_null, which to me indicates that there's a possibility of Declaration being null, but you never check it.

110–118

In essence, this looks like

if (/* Calculated stack usage so far*/ > StackUsageLimit)
  generateError(/*...*/);

but to me it's very obfuscated. Can you please either add more comments or move this to a separate function?

132–136

Same issue here. It would be better just to see something like int CurrentStackUsage = getCurrentStackUsage(C);

lib/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.cpp

17

#include "StackUsageMeasuringVisitor.h"

22–23

Constant static data members should be in-class initialized. https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#Rc-in-class-initializer

60

// end of anonymous namespace

61

//===----------------------------------------------------------------------===//
// Methods for StackUsageMeasuringVisitor.
//===----------------------------------------------------------------------===//

64–65

To me it seems like ContinueTraversing always equals to !ExitFlag. Maybe remove one of them?

77

https://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

104

https://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

[Szelethus]

I think the idea for a checker like this is great! I left some inline comments, but most of them are minor nits. I have some general remarks to make however:

• Your code lacks comments, especially a nice documentation describing this problem, how you approach it, what the general algorithm is etc. For example, you use Usage extensively, but I am still a little unsure what the difference is between Empty and EmptyFlagged. I'd encourage you to look at a couple nice examples:
  1. @baloghadamsoftware's [[ https://github.com/llvm-mirror/clang/blob/master/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp | IteratorChecker]] (A long code with fairly long comments to support it),
  2. @rnkovacs's [[https://github.com/llvm-mirror/clang/blob/master/lib/StaticAnalyzer/Checkers/DeleteWithNonVirtualDtorChecker.cpp | DeleteWithNonVirtualDtorChecker ]] (A shorter code with shorter explanation),
  3. My [[ https://github.com/llvm-mirror/clang/tree/master/lib/StaticAnalyzer/Checkers/UninitializedObject | UninitializedObjectChecker ]] (Very similar to your checker in terms of quantity of files etc)

• Make sure you follow the LLVM Coding Standards.
• As stated before, should move this to a new directory.
• For the amount of checker implementation you have, there aren't no many test cases. I can see that you handle CXXTryStmt, but there are no test cases for it.
• This revision is way too large for comfortable reading, you can help this by learning from my mistake and split it up into smaller patches. @NoQ summarized the reasons for this very nicely here: D45532#1083670
  1. Post a checker class with an empty callback [1]. Even in this stage, some discussion could be had with the general direction the implementation should go. This avoids the potential of investing a lot of effort into a project that could be wrong from the get-go. Don't get me wrong, I'm not at all saying this is the case here!
  2. Add implementation for checking a very easy case, such as a function with 10 array declarations, each having an absurd size.
  3. Add each new functionality as a separate patch, and add dependencies with "Edit Related Revisions". For example, one for handling branches, one for loops, etc.

Let me emphasize that I'm a beginner myself, so I could be wrong on many of these ^-^

[1] This could be a nice first patch:

//=======- StackSizeChecker.cpp ----------------------------------*- C++ -*-==//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//  This file defines a checker that checks for suspiciously high stack use.
//  The checker produces a warning whenever the given stack limit is exceeded.
//  The limit is defined by the "StackUsageLimit" analyzer parameter,
//  or defaults to 100000 bytes.
//
//===----------------------------------------------------------------------===//

class StackSizeChecker
    : public Checker<check::PreCall, check::PostCall, check::EndFunction> {
  mutable std::unique_ptr<BugType> StackOverflowBugType;

public:
  int StackUsageLimit;

  void checkPreCall(const CallEvent &Call, CheckerContext &C) const {}
  void checkPostCall(const CallEvent &Call, CheckerContext &C) const {}
  void checkEndFunction(CheckerContext &C) const {}
};

void clang::ento::registerStackSizeChecker(CheckerManager &Mgr) {
  StackSizeChecker *Check = Mgr.registerChecker<StackSizeChecker>();
  Check->StackUsageLimit = Mgr.getAnalyzerOptions().getOptionAsInteger(
      "StackUsageLimit", /*DefaultVal*/ 100000, Check);
}

include/clang/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.h

30

To me, Usage seems to be a way too general name. Also, for a class being used this heavily, it has no comments explaining what it does. Is this a property of a variable? A function call?

46

Which tree? I know you refer to the statement tree after reading the code for a while, but it would be more obvious if you put some comments for Usage.

94–131

Actually, it might be cleaner to move these into a new class, and have StackUsageMeasuringVisitor manage an object from that class.

102–111

Would isEmptyFlagged be a better method name?

124

The function name states sizeInBytes, but

• ASTContext::getTypeSizeInChars returns the width in CharUnits,
• which you divide with Context.getCharWidth(), which is in bits (according to the doxygen comments),
• and we end up getting the amount of bytes T occupies?

I might make a fool out of myself, but wouldn't the formula look something like this: (Context.getTypeSize(T) * Context.getCharWidth()) / 8?

135–138

Needs explanation.

lib/StaticAnalyzer/Checkers/StackSizeChecker.cpp

46

Why initialize here if you're going to overwrite it when you register the checker?

54

I think this would be better as static with the definition being out-of-line on the bottom of the file (but not before registering the checker, as it's traditionally the last function in the checker's TU).

68–77

Actually, same here, should be static and defined out of line, so the declarations and documentation can be placed on top of the file and implementation can be found on the bottom.

157–158

"StackUsageLimit", /*DefaultVal*/ 100000, Check);

lib/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.cpp

22–23

Actually, these shouldn't be static variables, but rather static functions (and probably within the class definition):

static Usage getEmptyUsage() { return Usage{0, 0, false, false}; }
static Usage getEmptyFlaggedUsage() { return Usage{0, 0, false, true}; }

37–39

I think this would be more fitting as a static member function.

41

I don't really understand what this function does.

109

getReturnExpressionSize?

153

Can you rephrase this? "signal the algorithm" doesn't sound too descriptive to me.

test/Analysis/stack-size-callchain.cpp

1

We only started doing this recently, but you can actually organize the run line like this:

// RUN: %clang_cc1 -analyze -analyzer-checker=core,alpha.core.StackSize \
// RUN:   -analyzer-config alpha.core.StackSize:StackUsageLimit=200 \
// RUN:   -std=c++11 -triple x86_64-unknown-linux-gnu -verify %s

[Szelethus]

lib/StaticAnalyzer/Checkers/StackSizeChecker.cpp

104

Ah, I I guess it's actually the height of the statement tree.

[Szelethus]

lib/StaticAnalyzer/Checkers/StackSizeChecker.cpp

19

Oh never mind, you had it in include/clang/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.h. I bet it is for the clang-tidy check. Never mind.

lib/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.cpp

17

Never mind, but should use "" instead of <>.

[lebedev.ri]

Without seeing the full picture (i.e. what you want to do with the clang-tidy check) it is hard to tell,
but are you *very* sure all this logic should be in clang/lib/StaticAnalyzer/, and not in clang/lib/Analysis/ ?

[mate1214]

Hi @Szelethus !

Thanks for all your detailed and helpful input, I will make sure to go over all the comments and answer them, but it will take some time.

A bit more background information on this checker and how it came to be might help you and others to understand some of the choices I made, and also address some of your general questions and worries.
I was hesitant about putting too much in the summary but it seems I should have added more.

This was a university assignment and I was encouraged to put it up here. This code has seen quite a few iterations and criticism.
It was my introduction to the clang tool-chain, and the clang-tidy checker was actually the first one to exist. Explaining it briefly will help with the "bigger picture".
It focused on single function bodies and could tell you how much the maximal stack space that body can occupy is.
It was able to calculate with:

• variable lifetimes (even taking into account lifetimes extended by const references etc.)
• recycled space (if the lifetime of a variable ends you can place the new ones can take up its place)
• execution rules (for example: if there is an if statement then you take the maximal space from its branches and not add them together etc.).
• variable length arrays (it took note when it saw one and if the resulting number was close enough to the limit but not over it you still got a warning)

The final result was the all-time maximum so if you had a ... {... char c[1000]; ...} ... somewhere in the middle that was, by lifetime rules, gone by the end and nothing surpassed it, you still got the correct numbers.
To produce the result, 2-3 massive recursive functions with tons of else if-s were used to traverse the AST of the function body with an in-order traverse strategy.
Now for ordinary functions it was an easy "traverse it all then get the final number" task. But enter the templates. There seemed to be no way to tell right away that we entered a function that had dependent types.
The easiest answer to templates was going until you see something that has dependent types involved then quit right away and say "it is a template we have nothing to do here".
The implementation was crude but it got the job done. It had (and still has) tests for most of the cases (statement types, expressions, VLA, templates etc.) and those tests felt natural there because they were concerned
with the contents of a particular function body.

Now single functions are fun, but entire call chains are what usually matter. You can pack a few char[10000]-s in one body but having them in each function of a call stack may not be so good idea.
So the static analyzer checker basically uses the same logic for single functions as mentioned before but as the analyzer follows the execution paths it adds up everything.
Now you could say that simply taking the whole bodies into account is enough but consider the following example:

void f(...){
    ... some minor stack space is used
    if(...) {
        start_a_deep_and_costly_calculation();
    } else {
        char x[5000];
        ....
    }
}

Here taking the whole body of f may yield 5000+"someting" bytes, instead of the actual small space, that gets used in the call stack when the condition is true and the other function gets called.
So it is reasonable to say that partial summaries should be possible up to certain point in the body.
Having said these and the fact that the original code was even harder to read, the StackUsageMeasuringVisitor came into existence to replace those massive recursive functions.
It is based on the RecursiveASTVisitor and uses post-order traverse strategy to accomplish its goals. This is where the readability over performance aspect comes in.
Without going too deep into details my visitor assigns Usage values to the AST nodes and then their parents can calculate with that, depending on what they actually are. The aforementioned requirement to stop on templates is quite easy,
because you do not need a real answer at the end so you can stop. The requirement to leave out the parts after a certain point is trickier, because it has to assign a value to all the nodes up to the top for proper calculations.
With the specifics of the visitor base class (I've seen no in-order traverse possibility), the solution was to assign zero to everything we do not care about and basically after a certain point it is a dry run on the rest of the function body and some calculation in the parent nodes.
I saw a question about that ContinueTraversing and ExitFlag in the visitor. They are both needed, because you can use the same logic for "I don't care about anything following this statement" and "I don't care about anything if I see a template type"
with some predicates, but in the first case you still need to do stuff with the post-order strategy and can not stop the visitor right away.
Also I saw a comment about Usage::Empty and Usage::EmptyFlagged, the first one says something uses no space at all in general, the second one says that it may, but it is considered zero by decision and nothing should change that (i.e.: visiting the same node again but as a subclass of the statement or expression type).
The rest of this SA checker is basically "use the visitor on every function body you enter and add the numbers to the global picture".

I'm contradicting my previous example here a bit, but if you take the SA approach, probably what you are *really* interested in the grand picture is the fact that the checker can follow the execution path and not make too big mistakes during calculations.
That is what the currently included tests try to aim for. The real "nit picky" ones like const references or ones about casts and such are left in the tidy checker. There you are really interested in them because you want to really focus on one function at a time and get the best possible result.
I realize this breakdown might not be the best, and anyone is welcome to suggest a proper test layout. The other concern I had about tests is the fact that these warnings contain numbers that the checker has to match exactly with the ones in the test, and sometimes it feels a bit forced to require exactly 238 bytes in the message instead of "somewhere between 230-250" if we are talking about some f --> g --> h call graph. I'm fine with doing the "exact" math for a single function f but it gets redundant and cumbersome.
Also if someone says for example that something that has been assumed to take up some space on the stack should just be zero because clang always optimizes it out no matter what (just a thought, but may happen with the various types of casts that the AST can include), then you may have to recalculate more tests than it should be necessary. Again if I have slipped over some fact about the capabilities of the testing system please correct me.

About your suggestion with the folder, it seems reasonable, but I'm not sure about the name.

I hope this helps some of the general questions, I will post other answers as I get to them. Thanks again for your comments!

[mate1214]

Hi @lebedev.ri!

Thanks for the question. I was not sure as to where exactly put the files. The important thing for me is that the StackUsageMeasuringVisitor should be reachable from the clang-tidy checker. (For the bigger picture please refer to my answer to @Szelethus). I was not able to find documentation I could use to put the extra logic in the right place (may be my fault). Any suggestions and references are welcome!

[lebedev.ri]

In D52390#1243228, @mate1214 wrote:

Hi @lebedev.ri!

Thanks for the question. I was not sure as to where exactly put the files. The important thing for me is that the StackUsageMeasuringVisitor should be reachable from the clang-tidy checker. (For the bigger picture please refer to my answer to @Szelethus). I was not able to find documentation I could use to put the extra logic in the right place (may be my fault). Any suggestions and references are welcome!

Reachable *how*?
Is clang-tidy check using this very same logic?
For recent examples, see ExprMutationAnalyzer, how it is structured (especially the tests, they are so nice!).
It started in clang-tidy, but then was promoted to analysis/.
So i'm wondering if the same should happen here, too.

[Szelethus]

Thanks for all your detailed and helpful input, I will make sure to go over all the comments and answer them, but it will take some time.

Cheers! I can't emphasize enough however that I might be wrong on what I've said, or say in this comment.

It was my introduction to the clang tool-chain

I always struggled getting enough literature about the static analyzer, if you didn't come across these works already, it might be worth taking a look :)

1. http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf
2. https://github.com/llvm-mirror/clang/blob/master/lib/StaticAnalyzer/README.txt
3. https://clang-analyzer.llvm.org/checker_dev_manual.html
4. https://github.com/llvm-mirror/clang/blob/master/docs/analyzer/RegionStore.txt
5. https://github.com/haoNoQ/clang-analyzer-guide/releases/download/v0.1/clang-analyzer-guide-v0.1.pdf <--- by far the best guide for the static analyzer at the moment.
6. https://github.com/llvm-mirror/clang/blob/master/docs/analyzer/IPA.txt

A bit more background information on this checker and how it came to be might help you and others to understand some of the choices I made, and also address some of your general questions and worries.
I was hesitant about putting too much in the summary but it seems I should have added more.

Summaries are one thing, that most likely won't be (and shouldn't have to be) read by a future maintainer, the code should speak for itself.

This was a university assignment and I was encouraged to put it up here. This code has seen quite a few iterations and criticism.

It's great that you put it up here! New checkers (which from what I've seen are mostly written by beginners) tend to go through in some cases a many month long review process, so I guess be prepared for some back and forth, but I personally really enjoyed the process, I hope you will too.

I have read the rest of your comment, thanks for the details! I can't say that I understand every aspect of your algorithm, but I have a couple question for the grand picture (but feel free to correct me if I misunderstood anything):

I can see that you use check::PreCall, check::PostCall, check::EndFunction, and you also modifiy the program state to have a fairly good idea about what execution path did the analyzer take, but a function's stack usage is calculated very roughly. Let's imagine that in the next example, f is only called after heavy stack usage:

// Let's just pretend that this function actually
// has a meaningful implementation that the analyzer
// knows will return false in this case.
bool hasStackEnoughSpace() { return false; }

void f() {
  if (hasStackEnoughSpace())
    // use the stack like an absolute madman
  else
    chill();
}

This is silly, but what it wants to demonstrate, that you could report a false positive here, despite the analyzer potentially knowing that that path will never be taken. To me it seems like you don't utilize the actual ProgramState, but I think you should( edit: nvm, partially, see my next comment).

To me it also seems like that you pretty much reinvent the compiler in this patch, by modeling almost everything the compiler does by itself. I'm sadly nowhere near an expert on this topic, but it begs the question whether there's an already existing solution to this. Let's wait for others to weigh in on this, maybe I'm wrong and this is what has to be done.

A couple tips for easier development and review process:

• I think before deep diving into the fixes, you really should split up this patch into an empty callback (essentially an announcement), and add each feature as a separate patch. Ideally, each time you implement a new feature, such as handling branches, you should make a neat patch with a small implementation and related test cases. As a beginner (and I suffered from this myself) this is exceptionally hard to do, because you can often find yourself deleting everything and starting all over, but I've grown to appreciate this principle as I often saved myself a whole lot of effort due to some feedback. However, making a rough proof of concept is in this case IMO a good idea, because it's hard to see at the start where the code will end up, but later it should be split up.
• Comment everything. I mean, bool isSuccessful() const { return IsSuccessful; } and similar functions speak for themselves, but ideally every non-trivial function and structure should be documented, as well as any non-trivial hackery inside a function.

[Szelethus]

One important thing I forgot, that you cant rely on ProgramState due to tidy's constraints. Btw, how do you plan to make this into a tidy checker? To me it seems like it would amplify the already existing false positive issues (if I understand your currect way of thinking correctly).

[whisperity]

One final nit apart from a few in-line comments (most of them are just arguing with @Szelethus anyways 😛): KB vs. KiB (remember how a 2 TB hard drive appears as 1.8 TB on your machine? Because it's TiB!) is one of my pet peeves especially that Windows and most people still get it wrong nowadays (and they also teach it wrong). Can we change the default from 100 000 to 102 400? That would make it truly 100 KiB in the proper sense.

include/clang/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.h

16

Speaking of missing header guards and in general: apart from tests, it might be a good idea to run CSA and Clang-Tidy on your checker's code. E.g. Tidy has a [[ https://clang.llvm.org/extra/clang-tidy/checks/llvm-header-guard.html | llvm-header-guard ]] checker -- which might not find this particular issue, but in general we could find some issues on this code itself.

(For the ultimate version, run your own checker on your own checker's code... maybe you yourself used a too large stack somewhere! 😜 )

102–111

Then calling this method would mean answering this question: "A Stmt/Decl is empty flagged?" This is a "What?" moment.

117

If we're talking about sizes, int (especially because it's signed int) might not be the most appropriate return type for these functions.

124

Need to make a distinction whether or not we want to use byte in the sense of 8 bit or in the sense of sizeof(char). Also, the code calls getTypeSize, not getTypeSizeInChars. This gives the answer in pure bits.

(Because of this, your suggested formula is wrong. getTypeSize() is already in bits, which you multiply further by getCharWidth() -- which is on some systems 8 -- then you divide it out. In most conventional systems the division cancels out the multiplication, and on systems where a sizeof(char)-byte is not 8, you'll get a non-integer quotient truncated as result.)

So:

• in case of you want to define byte to be 8 bits forever and always, the divisor should be 8, not getCharWidth().
• In case you want to define byte to be sizeof(char), then the current code is correct, but you could just use: [[ https://clang.llvm.org/doxygen/classclang_1_1ASTContext.html#aa8c44e88d6ce9b3cce885b62d3cd5dff | Context.getTypeSizeInChar() ]] . [[ https://clang.llvm.org/doxygen/classclang_1_1CharUnits.html#a968b1a66a449ab256c4dd176bd663c07 | getQuantity() ]].

Just for the record: the C++14 standard says the following in § 1.7 intro.memory:

The fundamental storage unit in the C++ memory is the byte. A byte is at least large enough to contain any member of the basic execution character set (-> § 2.3 lex.charset) and the eight-bit code units of the Unicode UTF-8 encoding form and is composed of a contiguous sequence of bits, the number of which is implementation-defined.

(lex.charset is basically an ASCII subset of 96 cardinality, lowercase, uppercase, parens, etc.)

I'm not sure what the convention is for error reports when referring to bytes, but maybe it would be better to consider byte in the C++ sense and let the value change based on what target the analyzer file is being compiled for.

lib/StaticAnalyzer/Checkers/StackSizeChecker.cpp

25

Note that using the other stream headers (<sstream> for example) is not problematic in this regard

41

generateError is const-qualified but writes this.

112

const_cast catches the eye. Why do you need to make this non-const?

test/Analysis/stack-size.cpp

3

Could we use int32_t instead of int, and uint8_t instead of bool?

[Szelethus]

include/clang/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.h

102–111

Right. And it doesn't actually describe what the function does. hasEmptyFlaggedSubDecl?

lib/StaticAnalyzer/Checkers/StackSizeChecker.cpp

25

Oh, right, sorry about that. In either case, every other checker uses LLVM streams, so I guess llvm::raw_*_ostream are the preferred stream classes anyways.

41

But I'm not sure that it should. At least, when I wrote my checker, I didn't have to: https://github.com/llvm-mirror/clang/blob/master/lib/StaticAnalyzer/Checkers/UninitializedObject/UninitializedObjectChecker.cpp#L166

[NoQ]

@Szelethus, thank you a lot for covering this review!

@mate1214, yes, please please split this up, like @Szelethus described.

At the moment this patch is not only huge, it is very under-tested. Eg., the Visitor promises support for C++ temporaries (which can potentially be a very difficult problem), but tests don't contain even a single class. If the functionality was added incrementally, it would have been easy to make sure every improvement is covered by regression tests.

Am i understanding correctly that the visitor is capable of summing up stack usage on the current path, i.e. ignoring objects that are put on the stack only within parts of the function that were not in fact executed on the current path, while also ignoring objects that are already removed from the stack? It should indeed be possible to accomplish this by only looking at the AST (unless VLAs or alloca() calls are used excessively), but in this case why is the checkEndFunction() callback not specifying the current path?

I guess a good idea for this checker would be to add a BugReporterVisitor to it in order to highlight where exactly does the stack usage go up. It is allowed to be slow, so it might be reasonable to just outright re-run the Visitor on every statement in the bug path.

I approve moving the visitor into lib/Analysis. That's indeed the library into which we dump all static analysis that is not specific to Static Analyzer.

Once out of alpha, this checker will look great in optin.performance, where we already have a checker for excessive structure padding.

include/clang/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.h

28

It's Entomology.

[NoQ]

In D52390#1251526, @NoQ wrote:

I approve moving the visitor into lib/Analysis. That's indeed the library into which we dump all static analysis that is not specific to Static Analyzer.

@rsmith disagrees though, and he has a point: http://lists.llvm.org/pipermail/cfe-commits/Week-of-Mon-20181001/245294.html

Let's keep this in lib/StaticAnalyzer then!

[Szelethus]

It'd also be good to have an entry in www/analyzer/alpha_checks.html. We've been neglecting it for long enough :/.

[mate1214]

Hi!

Sorry for the delay. After considering the amount of requested tests and investigating the possibly reviewer friendly ways to split this up, I came to the conclusion that I can not go through with all this work for now. Thank you everyone who took the time to comment.
I'm abandoning this revision.

include/clang/StaticAnalyzer/Checkers/Checkers.td

 def NonnullGlobalConstantsChecker: Checker<"NonnilStringConstants">,
   HelpText<"Assume that const string-like globals are non-null">,
   DescFile<"NonilStringConstantsChecker.cpp">;
 
 } // end "core"
 
 let ParentPackage = CoreAlpha in {
 
+def StackSizeChecker : Checker<"StackSize">,
+  HelpText<"Warn if estimated stack usage exceeds the StackUsageLimit parameter (measured in bytes, defaults to 100000)">,
+  DescFile<"StackSizeChecker.cpp">;
+
 def BoolAssignmentChecker : Checker<"BoolAssignment">,
   HelpText<"Warn about assigning non-{0,1} values to Boolean variables">,
   DescFile<"BoolAssignmentChecker.cpp">;
 
 def CastSizeChecker : Checker<"CastSize">,
   HelpText<"Check when casting a malloc'ed type T, whether the size is a multiple of the size of T">,
   DescFile<"CastSizeChecker.cpp">;
 

include/clang/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.h

+//==-- StackUsageMeasuringVisitor.h -------------------------------*- C++ -*--//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file declares the StackUsageMeasuringVisitor, a RecursiveASTVisitor
+//  based class for summarizing the stack usage of statement trees.
+//  It can calculate the complete usage of a tree or only a subtree up to
+//  the point where the given predicate becomes true.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/DenseMap.h"
+
+#include "clang/AST/ASTConsumer.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/Frontend/FrontendAction.h"
+#include "clang/Tooling/Tooling.h"
+#include <functional>
+#include <map>
+
+namespace clang {
+namespace stack {
+
+struct Usage {
+
+  Usage &operator+=(const Usage &U);
+
+  bool operator==(const Usage &U) const {
+    return Constant == U.Constant && Maximal == U.Maximal &&
+           DynAlloc == U.DynAlloc && ExitFlag == U.ExitFlag;
+  }
+
+  int Constant;  // The amount of used space that survives the statement,
+                 // important for variable declarations and temporaries extended
+                 // by const references.
+  int Maximal;   // Greater or equal to 'Constant', includes temporaries created
+                 // by the statement.
+  bool DynAlloc; // Flag for dynamic stack allocation in the statement or any of
+                 // its children.
+  bool ExitFlag; // Tells the visitor to cease consuming the tree.
+
+  static const Usage Empty, EmptyFlagged;
+};
+
+class StackUsageMeasuringVisitor
+    : public clang::RecursiveASTVisitor<StackUsageMeasuringVisitor> {
+
+public:
+  using Predicate = std::function<bool(const Stmt *)>;
+
+  explicit StackUsageMeasuringVisitor(ASTContext &Context)
+      : Context(Context), ContinueTraversing(true), ExitFlag(false),
+        HardExit(false), ForceTemporariesToConstant(false),
+        ExitPredicate(nullptr) {}
+
+  Usage collected() const;
+
+  // The visitor should traver post-order, because each node needs
+  // precalculated information in their children.
+  bool shouldTraversePostOrder() const { return true; }
+
+  bool VisitStmt(const Stmt *);
+
+  bool VisitDeclStmt(const DeclStmt *);
+  bool VisitExpr(const Expr *);
+  bool VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *);
+  bool VisitLambdaExpr(const LambdaExpr *);
+  bool VisitCXXThrowExpr(const CXXThrowExpr *);
+  bool VisitArraySubscriptExpr(const ArraySubscriptExpr *);
+  bool VisitCompoundStmt(const CompoundStmt *);
+  bool VisitIfStmt(const IfStmt *);
+  bool VisitSwitchStmt(const SwitchStmt *);
+  bool VisitForStmt(const ForStmt *);
+  bool VisitCXXForRangeStmt(const CXXForRangeStmt *);
+  bool VisitWhileStmt(const WhileStmt *);
+  bool VisitDoStmt(const DoStmt *);
+  bool VisitCXXTryStmt(const CXXTryStmt *);
+  bool VisitReturnStmt(const ReturnStmt *);
+  bool VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *);
+  bool VisitVarDecl(const VarDecl *);
+
+  Usage calculateFunctionUsage(const FunctionDecl *, Predicate, bool);
+  Usage sumFunctionUpUntil(const FunctionDecl *, const Stmt *);
+  Usage sumFunctionUpUntilTemplate(const FunctionDecl *);
+  Usage sumStmtWithTemporariesExtracted(const Stmt *);
+  Usage sumStmt(const Stmt *, Predicate, bool, bool);
+private:
+  void clear();
+  bool hasUsageStored(const Stmt *S) const {
+    return StmtSubtreeUsages.find(S) != StmtSubtreeUsages.end();
+  }
+  bool hasUsageStored(const Decl *D) const {
+    return DeclSubtreeUsages.find(D) != DeclSubtreeUsages.end();
+  }
+
+  bool hasEmptyFlaggedUsageStored(const Stmt *S) const {
+    auto iter = StmtSubtreeUsages.find(S);
+    return iter != StmtSubtreeUsages.end() &&
+           iter->second == Usage::EmptyFlagged;
+  }
+  bool hasEmptyFlaggedUsageStored(const Decl *D) const {
+    auto iter = DeclSubtreeUsages.find(D);
+    return iter != DeclSubtreeUsages.end() &&
+           iter->second == Usage::EmptyFlagged;
+  }
+  void putUsage(const Stmt *, Usage);
+  Usage retrieveUsage(const Stmt *) const;
+  void putUsage(const Decl *, Usage);
+  Usage retrieveUsage(const Decl *) const;
+
+  int varSize(const VarDecl *Var) const {
+    return Var->hasLocalStorage() * sizeInBytes(Var->getType());
+  }
+
+  int sizeInBytes(QualType T) const {
+    return T->isIncompleteType() || T->isPlaceholderType()
+               ? 0
+               : Context.getTypeSize(T) / Context.getCharWidth();
+  }
+  int exprRetSize(const Expr *) const;
+
+  ASTContext &Context;
+
+  llvm::DenseMap<const Stmt *, Usage> StmtSubtreeUsages;
+  llvm::DenseMap<const Decl *, Usage> DeclSubtreeUsages;
+
+  Stmt* rootStmt;
+
+  bool ContinueTraversing;
+  bool ExitFlag;
+  bool HardExit;
+  bool ForceTemporariesToConstant;
+
+  Predicate ExitPredicate;
+};
+
+} // stack
+} // clang

lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   PthreadLockChecker.cpp
   RetainCountChecker/RetainCountChecker.cpp
   RetainCountChecker/RetainCountDiagnostics.cpp
   ReturnPointerRangeChecker.cpp
   ReturnUndefChecker.cpp
   RunLoopAutoreleaseLeakChecker.cpp
   SimpleStreamChecker.cpp
   StackAddrEscapeChecker.cpp
+  StackSizeChecker.cpp
   StdLibraryFunctionsChecker.cpp
   StreamChecker.cpp
   TaintTesterChecker.cpp
   TestAfterDivZeroChecker.cpp
   TraversalChecker.cpp
   TrustNonnullChecker.cpp
   UndefBranchChecker.cpp
   UndefCapturedBlockVarChecker.cpp

lib/StaticAnalyzer/Checkers/StackSizeChecker.cpp

+//=======- StackSizeChecker.cpp ----------------------------------*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines a checker that checks for suspiciously high stack use.
+//  The checker produces a warning whenever the given stack limit is exceeded.
+//  The limit is defined by the "StackUsageLimit" analyzer parameter,
+//  or defaults to 100000 bytes.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/AST/StmtCXX.h"
+#include "clang/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.h"
+#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include <sstream>
+
+using namespace clang;
+using namespace clang::ento;
+
+namespace {
+
+struct StackInt {
+  int Used;
+  bool operator==(const StackInt &Other) const { return Used == Other.Used; }
+  void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Used); }
+  operator int() const { return Used; }
+};
+
+class StackSizeChecker
+    : public Checker<check::PreCall, check::PostCall, check::EndFunction> {
+  mutable std::unique_ptr<BugType> StackOverflowBugType;
+
+  void generateError(int NumBytes, SourceRange Range, CheckerContext &C) const;
+
+public:
+  StackSizeChecker() : StackUsageLimit(0) {}
+  int StackUsageLimit;
+
+  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
+  void checkEndFunction(CheckerContext &C) const;
+};
+
+int countPredecessors(const CheckerContext &C) {
+  const auto *Frame = C.getStackFrame()->getParent();
+  int N = 0;
+  while (Frame) {
+    const auto *D = dyn_cast_or_null<FunctionDecl>(Frame->getDecl());
+    if (D)
+      ++N;
+    else
+      break;
+    Frame = dyn_cast_or_null<StackFrameContext>(Frame->getParent());
+  }
+  return N;
+}
+
+int length(const llvm::ImmutableList<StackInt>& L) {
+  int N = 0;
+  auto I = L.begin();
+  auto E = L.end();
+  while(I != E){
+    ++N;
+    ++I;
+  }
+  return N;
+}
+}
+
+REGISTER_LIST_WITH_PROGRAMSTATE(StackSizeList, StackInt)
+
+void StackSizeChecker::generateError(int NumBytes, SourceRange Range,
+                                     CheckerContext &C) const {
+  ExplodedNode *ErrNode = C.generateNonFatalErrorNode();
+  // If we've already reached this node on another path, return.
+  if (!ErrNode)
+    return;
+
+  if (!StackOverflowBugType) {
+    StackOverflowBugType.reset(
+        new BugType(this, "Stack overuse", "Program error"));
+  }
+  // Generate the report.
+  std::ostringstream ErrorMessage;
+  ErrorMessage << "Estimated stack usage is " << NumBytes << " bytes";
+  auto R = llvm::make_unique<BugReport>(*StackOverflowBugType,
+                                        ErrorMessage.str(), ErrNode);
+  R->addRange(Range);
+  C.emitReport(std::move(R));
+}
+
+void StackSizeChecker::checkEndFunction(CheckerContext &C) const {
+  ProgramStateRef State = C.getState();
+  auto StackLevels = State->get<StackSizeList>();
+  if (length(StackLevels) != countPredecessors(C))
+    return;
+  stack::StackUsageMeasuringVisitor Visitor(C.getASTContext());
+  auto Declaration =
+      dyn_cast_or_null<FunctionDecl>(C.getLocationContext()->getDecl());
+  int NumBytes =
+      Visitor
+          .sumFunctionUpUntilTemplate(const_cast<FunctionDecl *>(Declaration))
+          .Maximal;
+  if (!StackLevels.isEmpty())
+    NumBytes += StackLevels.getHead();
+
+  if (NumBytes > StackUsageLimit)
+    generateError(NumBytes, Declaration->getSourceRange(), C);
+}
+
+void StackSizeChecker::checkPreCall(const CallEvent &Call,
+                                    CheckerContext &C) const {
+  ProgramStateRef State = C.getState();
+  auto StackLevels = State->get<StackSizeList>();
+  if (length(StackLevels) != countPredecessors(C))
+    return;
+
+  stack::StackUsageMeasuringVisitor Visitor(C.getASTContext());
+
+  auto *Declaration =
+      dyn_cast_or_null<FunctionDecl>(C.getLocationContext()->getDecl());
+  int NumBytes =
+      Visitor.sumFunctionUpUntil(Declaration, Call.getOriginExpr()).Constant +
+      Visitor.sumStmtWithTemporariesExtracted(Call.getOriginExpr()).Constant;
+  if (!StackLevels.isEmpty())
+    NumBytes += StackLevels.getHead();
+
+  if (NumBytes > StackUsageLimit) {
+    generateError(NumBytes, Call.getSourceRange(), C);
+  }
+  State = State->add<StackSizeList>({NumBytes});
+  C.addTransition(State);
+}
+
+void StackSizeChecker::checkPostCall(const CallEvent &Call,
+                                     CheckerContext &C) const {
+  ProgramStateRef State = C.getState();
+  auto StackLevels = State->get<StackSizeList>();
+  if (length(StackLevels) != countPredecessors(C) + 1)
+    return;
+  State = State->set<StackSizeList>(StackLevels.getTail());
+  C.addTransition(State);
+}
+
+void clang::ento::registerStackSizeChecker(CheckerManager &Mgr) {
+  StackSizeChecker *Check = Mgr.registerChecker<StackSizeChecker>();
+  Check->StackUsageLimit = Mgr.getAnalyzerOptions().getOptionAsInteger(
+      "StackUsageLimit", 100000, Check);
+}

lib/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.cpp

+//==-- StackUsageMeasuringVisitor.cpp -----------------------------*- C++ -*--//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines the StackUsageMeasuringVisitor, a RecursiveASTVisitor
+//  based class for summarizing the stack usage of statement trees.
+//  It can calculate the complete usage of a tree or only a subtree up to
+//  the point where the given predicate becomes true.
+//
+//===----------------------------------------------------------------------===//
+
+#include <clang/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.h>
+
+namespace clang {
+namespace stack {
+
+const Usage Usage::Empty = {0, 0, false, false};
+const Usage Usage::EmptyFlagged = {0, 0, false, true};
+
+Usage &Usage::operator+=(const Usage &U) {
+  if (ExitFlag)
+    return *this;
+  Maximal = std::max(Maximal, Constant + U.Maximal);
+  Constant += U.Constant;
+  DynAlloc = DynAlloc || U.DynAlloc;
+  ExitFlag = ExitFlag || U.ExitFlag;
+  return *this;
+}
+
+namespace {
+
+Usage withoutConstant(Usage U) {
+  return {0, U.Maximal, U.DynAlloc, U.ExitFlag};
+}
+
+bool countsAsZero(const Expr *Ex) {
+  auto Cls = Ex->getStmtClass();
+  return Cls == Stmt::StmtClass::DeclRefExprClass ||
+         Cls == Stmt::StmtClass::MemberExprClass ||
+         Cls == Stmt::StmtClass::CharacterLiteralClass ||
+         Cls == Stmt::StmtClass::CXXBoolLiteralExprClass ||
+         Cls == Stmt::StmtClass::CXXNullPtrLiteralExprClass ||
+         Cls == Stmt::StmtClass::FloatingLiteralClass ||
+         Cls == Stmt::StmtClass::ImaginaryLiteralClass ||
+         Cls == Stmt::StmtClass::IntegerLiteralClass ||
+         Cls == Stmt::StmtClass::StringLiteralClass;
+}
+
+bool isTypeDependent(const Stmt *S) {
+  if (const auto *E = dyn_cast<Expr>(S)) {
+    return E->isTypeDependent();
+  }
+  return false;
+}
+}
+
+void StackUsageMeasuringVisitor::putUsage(const Stmt *S, Usage U) {
+  if (U.ExitFlag) {
+    ExitFlag = true;
+    ContinueTraversing = !HardExit;
+  }
+  StmtSubtreeUsages[S] = U;
+}
+
+Usage StackUsageMeasuringVisitor::retrieveUsage(const Stmt *S) const {
+  if (S == nullptr)
+    return Usage::Empty;
+  auto Iter = StmtSubtreeUsages.find(S);
+  if (Iter != StmtSubtreeUsages.end()) {
+    Usage U = Iter->second;
+    return U;
+  } else {
+    return Usage::Empty;
+  }
+}
+
+void StackUsageMeasuringVisitor::clear() {
+  StmtSubtreeUsages.clear();
+  DeclSubtreeUsages.clear();
+  ExitFlag = false;
+  ContinueTraversing = true;
+}
+
+void StackUsageMeasuringVisitor::putUsage(const Decl *D, Usage U) {
+  if (U.ExitFlag) {
+    ExitFlag = true;
+    ContinueTraversing = !HardExit;
+  }
+  DeclSubtreeUsages[D] = U;
+}
+
+Usage StackUsageMeasuringVisitor::retrieveUsage(const Decl *D) const {
+  if (D == nullptr)
+    return Usage::Empty;
+  auto Iter = DeclSubtreeUsages.find(D);
+  if (Iter != DeclSubtreeUsages.end()) {
+    Usage U = Iter->second;
+    return U;
+  } else {
+    return Usage::Empty;
+  }
+}
+
+int StackUsageMeasuringVisitor::exprRetSize(const Expr *E) const {
+  auto StmtCls = E->getStmtClass();
+  // If it's a NoOp expression the returned value does not use extra space.
+  // Also constructors and 'ExprWithCleanups' expressions are assumed to have
+  // no extra return space costs.
+  if (E->IgnoreParenNoopCasts(Context) != E ||
+      StmtCls == Stmt::StmtClass::ExprWithCleanupsClass ||
+      StmtCls == Stmt::StmtClass::CXXConstructExprClass) {
+    return 0;
+  }
+  return sizeInBytes(E->isLValue()
+                         ? Context.getLValueReferenceType(E->getType())
+                         : E->getType());
+}
+
+bool StackUsageMeasuringVisitor::VisitStmt(const Stmt *S) {
+  // This will flag the statement or expression if it is the desired one.
+  if (ExitPredicate(S)) {
+    putUsage(S, Usage::EmptyFlagged);
+  }
+  return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitDeclStmt(const DeclStmt *D) {
+  if (!hasEmptyFlaggedUsageStored(D)) {
+    Usage Summary = Usage::Empty;
+    // Summarize the variable declarations and their initializing expressions.
+    for (const auto *Dec : D->getDeclGroup()) {
+      Usage Var = retrieveUsage(Dec);
+      Summary += Var;
+      if (Var.ExitFlag)
+        break;
+    }
+    putUsage(D, Summary);
+  }
+  return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitVarDecl(const VarDecl *D) {
+  if (!hasEmptyFlaggedUsageStored(D)) {
+    if (D->isInvalidDecl()) {
+      // Invalid declarations count as zero.
+      putUsage(D, Usage::Empty);
+    } else if (D->getType()->isDependentType()) {
+      // A template declaration was found, signal the algorithm.
+      putUsage(D, Usage::EmptyFlagged);
+    } else {
+      int VarSize = varSize(D);
+      Usage Var = {VarSize, VarSize, D->getType()->isVariableArrayType(),
+                   false};
+      Usage Init = retrieveUsage(D->getInit());
+      Init.Maximal -= VarSize * isa<ArrayType>(D->getType());
+      Var += Init;
+      putUsage(D, Var);
+    }
+  }
+  return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitExpr(const Expr *Ex) {
+  if (!hasEmptyFlaggedUsageStored(Ex)) {
+    Usage Summary = Usage::Empty;
+    if (!countsAsZero(Ex)) {
+      for (const auto &Child : Ex->children()) {
+        // The way we summarize the subexpressions is special here,
+        // because all of the temporary objects remain until the end of the
+        // execution of the whole line.
+        Usage U = retrieveUsage(Child);
+        Summary.Constant += U.Constant;
+        Summary.Maximal += U.Maximal;
+        Summary.DynAlloc = Summary.DynAlloc || U.DynAlloc;
+        Summary.ExitFlag = Summary.ExitFlag || U.ExitFlag;
+        if (Summary.ExitFlag)
+          break;
+      }
+      Summary.Maximal += exprRetSize(Ex);
+    }
+    putUsage(Ex, Summary);
+  }
+  return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitMaterializeTemporaryExpr(
+    const MaterializeTemporaryExpr *Ex) {
+  if (!hasEmptyFlaggedUsageStored(Ex)) {
+    // We have a temporary object whose lifetime may be extended by a constant
+    // reference.
+    auto *Temporary = Ex->GetTemporaryExpr();
+
+    Usage U = retrieveUsage(Temporary);
+    if (ForceTemporariesToConstant) {
+      // In this case, we force all the temporaries into the constant usage
+      // if they are not held by static references. This way of calculation
+      // is useful for summarizing an expression locally.
+      int Constant =
+          (Ex->getStorageDuration() != SD_Static) *
+          sizeInBytes(Temporary->IgnoreParenNoopCasts(Context)->getType());
+      U.Constant += Constant;
+    } else {
+      // Usually we count constant usage only if there is a non-static variable
+      // declaration that keeps the temporary alive.
+      int Constant =
+          (Ex->getExtendingDecl() && Ex->getStorageDuration() != SD_Static)
+              ? exprRetSize(Temporary)
+              : 0;
+      U.Constant += Constant;
+    }
+    U.Maximal = std::max(U.Maximal, U.Constant);
+    putUsage(Ex, U);
+  }
+  return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitLambdaExpr(const LambdaExpr *Ex) {
+  if (!hasEmptyFlaggedUsageStored(Ex)) {
+    // In this case we are only interested in the result type,
+    // the body is checked as a separate function by the checker.
+    int Result = exprRetSize(Ex);
+    putUsage(Ex, {0, Result, false, false});
+  }
+  return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitCXXThrowExpr(const CXXThrowExpr *Ex) {
+  if (!hasEmptyFlaggedUsageStored(Ex)) {
+    // We assume no 'constant' stack usage here.
+    Usage Sub = retrieveUsage(Ex->getSubExpr());
+    putUsage(Ex, {0, Sub.Maximal, Sub.DynAlloc, Sub.ExitFlag});
+  }
+  return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitArraySubscriptExpr(
+    const ArraySubscriptExpr *Ex) {
+  if (!hasEmptyFlaggedUsageStored(Ex)) {
+    // We assume no extra usage for array elements, but the way the are reached
+    // may create extra usage.
+    Usage Base = retrieveUsage(Ex->getBase());
+    Usage Idx = retrieveUsage(Ex->getIdx());
+    putUsage(Ex, {Base.Constant + Idx.Constant, Base.Maximal + Idx.Maximal,
+                  Base.DynAlloc || Idx.DynAlloc, Idx.ExitFlag});
+  }
+  return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitCompoundStmt(const CompoundStmt *CS) {
+  if (!hasEmptyFlaggedUsageStored(CS)) {
+    // The 'Constant' usage adds up from all the children,
+    // the 'Maximal' usage is the maximum of all children values.
+    Usage Summary = Usage::Empty;
+    for (const auto *Child : CS->body()) {
+      Summary += retrieveUsage(Child);
+      if (Summary.ExitFlag)
+        break;
+    }
+    // All the compound statements except for the function body have
+    // zero constant usage. In the function body constant usage can be
+    // used for partial summaries.
+    if (CS != rootStmt)
+      Summary.Constant = 0;
+    putUsage(CS, Summary);
+  }
+  return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitIfStmt(const IfStmt *If) {
+  if (!hasEmptyFlaggedUsageStored(If)) {
+    // The variables declared in the condition field exist during the execution
+    // of the chosen branch, but only one of the branches get executed,
+    // so we take the maximal one and add the condition.
+    // We also have to take into account the ExitFlags of the branches, so if
+    // a branch has less usage but is flagged, it must be the one we use.
+    Usage IfUsage = retrieveUsage(If->getInit());
+    const DeclStmt *Decl = If->getConditionVariableDeclStmt();
+    IfUsage += Decl ? retrieveUsage(Decl) : retrieveUsage(If->getCond());
+
+    Usage ThenUs = retrieveUsage(If->getThen());
+    Usage ElseUs = retrieveUsage(If->getElse());
+    // We have to choose the branch that has greater maximal usage or is
+    // flagged.
+    if (ThenUs.ExitFlag ||
+        (!ElseUs.ExitFlag && ThenUs.Maximal > ElseUs.Maximal)) {
+      IfUsage += ThenUs;
+    } else {
+      IfUsage += ElseUs;
+    }
+    putUsage(If, withoutConstant(IfUsage));
+  }
+  return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitSwitchStmt(const SwitchStmt *S) {
+  if (!hasEmptyFlaggedUsageStored(S)) {
+    // The the condition variable is handled like in the if statement,
+    // the body is treated as one big compound statement,
+    // since we are mainly interested in the maximal usage and declarations
+    // can't be case specific or they exist in substatements,
+    // where they go into the maximal usage.
+    Usage SwitchUsage = retrieveUsage(S->getInit());
+    const DeclStmt *Decl = S->getConditionVariableDeclStmt();
+
+    SwitchUsage += Decl ? retrieveUsage(Decl) : retrieveUsage(S->getCond());
+    SwitchUsage += retrieveUsage(S->getBody());
+
+    putUsage(S, withoutConstant(SwitchUsage));
+  }
+  return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitForStmt(const ForStmt *For) { // TODO
+  if (!hasEmptyFlaggedUsageStored(For)) {
+    // From the head only the loop variable exists during the execution of the
+    // body, but the subexpressions in the condition and the increment fields
+    // may affect the maximal usage.
+    Usage ForUsage = retrieveUsage(For->getInit());
+
+    const DeclStmt *Decl = For->getConditionVariableDeclStmt();
+    ForUsage += Decl ? retrieveUsage(Decl) : retrieveUsage(For->getCond());
+    ForUsage += retrieveUsage(For->getInc());
+    ForUsage += retrieveUsage(For->getBody());
+
+    putUsage(For, withoutConstant(ForUsage));
+  }
+  return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitCXXForRangeStmt(
+    const CXXForRangeStmt *For) {
+  if (!hasEmptyFlaggedUsageStored(For)) {
+    // Similar logic to the for statement, every hidden declaration is
+    // taken into account.
+    Usage ForRangeUsage = retrieveUsage(For->getLoopVarStmt());
+    ForRangeUsage += retrieveUsage(For->getBeginStmt());
+    ForRangeUsage += retrieveUsage(For->getEndStmt());
+    ForRangeUsage += retrieveUsage(For->getBody());
+    ForRangeUsage += retrieveUsage(For->getInc());
+    ForRangeUsage += retrieveUsage(For->getRangeStmt());
+
+    putUsage(For, withoutConstant(ForRangeUsage));
+  }
+  return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitWhileStmt(const WhileStmt *While) {
+  if (!hasEmptyFlaggedUsageStored(While)) {
+    // Similar logic to the for statement, head and body handled according to
+    // lifetime rules.
+    Usage WhileUsage = retrieveUsage(While->getCond());
+    WhileUsage += retrieveUsage(While->getBody());
+
+    putUsage(While, withoutConstant(WhileUsage));
+  }
+  return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitDoStmt(const DoStmt *DoWhile) {
+  if (!hasEmptyFlaggedUsageStored(DoWhile)) {
+    // Similar logic to the while statment, but taking into account that
+    // the lifetime of the variables in the body end before the condition
+    Usage DoWhileUsage = withoutConstant(retrieveUsage(DoWhile->getBody()));
+    DoWhileUsage += withoutConstant(retrieveUsage(DoWhile->getCond()));
+    putUsage(DoWhile, DoWhileUsage);
+  }
+  return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitCXXTryStmt(const CXXTryStmt *Try) {
+  if (!hasEmptyFlaggedUsageStored(Try)) {
+    // The maximal usage is calculated between try and except blocks.
+    // Try block allocations are assumed to be cleared before the execution of
+    // any handlers.
+
+    // Function bodies can be try statements. If this is the body, it needs
+    // constant usage statistic in case we do a partial summary.
+    bool isRootStmt = rootStmt == Try;
+    Usage TryUsage = isRootStmt
+                         ? retrieveUsage(Try->getTryBlock())
+                         : withoutConstant(retrieveUsage(Try->getTryBlock()));
+
+    for (unsigned i = 0; i < Try->getNumHandlers() && !TryUsage.ExitFlag; ++i) {
+      auto Dec = Try->getHandler(i)->getExceptionDecl();
+      int Hdecl = Dec ? varSize(Dec) : 0;
+      Usage HandlerBodyUsage =
+          isRootStmt ? retrieveUsage(Try->getHandler(i)->getHandlerBlock())
+                     : withoutConstant(retrieveUsage(
+                           Try->getHandler(i)->getHandlerBlock()));
+      HandlerBodyUsage.Maximal += Hdecl;
+      TryUsage += HandlerBodyUsage;
+    }
+    putUsage(Try, TryUsage);
+  }
+  return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitReturnStmt(const ReturnStmt *Return) {
+  if (!hasEmptyFlaggedUsageStored(Return)) {
+    putUsage(Return, retrieveUsage(Return->getRetValue()));
+  }
+  return ContinueTraversing;
+}
+
+bool StackUsageMeasuringVisitor::VisitUnaryExprOrTypeTraitExpr(
+    const UnaryExprOrTypeTraitExpr *Ex) {
+  if (!hasEmptyFlaggedUsageStored(Ex) && Ex->getKind() == UETT_SizeOf) {
+    // The sizeof expression is special case where the children are not
+    // evaluated during execution.
+    Usage Returned = Usage::Empty;
+    Returned.Maximal = exprRetSize(Ex);
+    Returned.Constant = 0;
+    Returned.ExitFlag = retrieveUsage(Ex).ExitFlag;
+    putUsage(Ex, Returned);
+  }
+  // Other cases are handled by the generic Expr branch.
+  return ContinueTraversing;
+}
+
+Usage StackUsageMeasuringVisitor::sumStmt(const Stmt *S, Predicate ExitPred,
+                                          bool Hard,
+                                          bool ForceTempsToConstant) {
+  HardExit = Hard;
+  ForceTemporariesToConstant = ForceTempsToConstant;
+  clear();
+  ExitPredicate = ExitPred;
+  TraverseStmt(const_cast<Stmt *>(S));
+  auto U = hasUsageStored(S) ? retrieveUsage(S) : Usage::EmptyFlagged;
+  return U;
+}
+
+Usage StackUsageMeasuringVisitor::calculateFunctionUsage(
+    const FunctionDecl *Func, Predicate ExitPred, bool Hard) {
+  if (!Func ||
+      Func->getTemplatedKind() != FunctionDecl::TemplatedKind::TK_NonTemplate ||
+      Func->isPure() || !Func->hasBody())
+    return Usage::EmptyFlagged;
+  int SizeCounter = 0;
+  for (const auto *Param : Func->parameters()) {
+    // It is no use calculating usage on templates.
+    if (Param->getType()->isDependentType())
+      return Usage::EmptyFlagged;
+    int ParamSize = sizeInBytes(Param->getType());
+    SizeCounter += ParamSize;
+  }
+  // then check the body.
+  auto *Body = Func->getBody();
+  rootStmt = Body;
+  Usage Us = sumStmt(Body, ExitPred, Hard, false);
+  Us.Maximal += SizeCounter;
+  Us.Constant += SizeCounter;
+  return Us;
+}
+
+Usage StackUsageMeasuringVisitor::sumFunctionUpUntil(const FunctionDecl *Func,
+                                                     const Stmt *Particular) {
+  return calculateFunctionUsage(
+      Func, [Particular](const Stmt *S) { return S == Particular; }, false);
+}
+
+Usage StackUsageMeasuringVisitor::sumFunctionUpUntilTemplate(
+    const FunctionDecl *Func) {
+  return calculateFunctionUsage(Func, isTypeDependent, true);
+}
+
+Usage StackUsageMeasuringVisitor::sumStmtWithTemporariesExtracted(
+    const Stmt *S) {
+  return sumStmt(S, isTypeDependent, false, true);
+}
+
+} // stack
+} // clang

test/Analysis/stack-size-callchain.cpp

+// RUN: %clang_cc1 -analyze -analyzer-checker=core,alpha.core.StackSize -analyzer-config alpha.core.StackSize:StackUsageLimit=200 -std=c++11 -triple x86_64-unknown-linux-gnu -verify %s
+
+// The checker accumulates variables from each level of the call chain.
+// In this case from function 'c' to 'a' each body has 10 long integers
+// on the stack, which accumulates to 30 * 8 = 240 bytes.
+
+void function_a() {
+  long A[10]; // expected-warning {{Estimated stack usage is 240 bytes}}
+}
+
+void function_b() {
+  long B1[10];
+  function_a();
+  long B2[5];
+}
+
+void function_c() {
+  long C1[10];
+  function_b();
+  long C2[5];
+}
+

test/Analysis/stack-size.cpp

+// RUN: %clang_cc1 -analyze -analyzer-checker=core,alpha.core.StackSize -analyzer-config alpha.core.StackSize:StackUsageLimit=1 -std=c++11 -triple x86_64-unknown-linux-gnu -verify %s
+
+// In this test an integer is 4 bytes, a bool is 1 byte.
+// The analysis uses the same method of calculation as the misc-stack-size
+// checker in clang-tidy.
+// (see clang-tools-extra/test/clang-tidy/misc-stack-size.cpp for examples)
+
+// If a call happens in a function body, the stack space used by the function
+// will be registered as the space used up until that point. Each time the
+// execution of a function body is completely finished, the maximal amount
+// of space used is estimated and checked against the limit.
+
+// This function gets called multiple times. The space used is varying each time.
+int f(int X) { return X; } // expected-warning {{Estimated stack usage is 8 bytes}}
+                           // expected-warning@-1 {{Estimated stack usage is 12 bytes}}
+
+// This function illustrates the partial summation ability.
+// Before each call, the stack usage at that point is registered,
+// so it can be added to the statistics of the called function.
+void linear() {
+  int X = 1;
+  f(X); // expected-warning {{Estimated stack usage is 4 bytes}}
+  int Y = 2;
+  f(Y); // expected-warning {{Estimated stack usage is 8 bytes}}
+} // expected-warning {{Estimated stack usage is 20 bytes}}
+
+// This function shows the ability of this checker to calculate with recursion
+// far as the analyzer follows it.
+void recursion(int N) {
+  int X;
+
+  if (N <= 0)
+    return; // expected-warning {{Estimated stack usage is 44 bytes}}
+
+  recursion(N - 1); // expected-warning {{Estimated stack usage is 8 bytes}}
+                    // expected-warning@-1 {{Estimated stack usage is 16 bytes}}
+                    // expected-warning@-2 {{Estimated stack usage is 24 bytes}}
+                    // expected-warning@-3 {{Estimated stack usage is 20 bytes}}
+                    // expected-warning@-4 {{Estimated stack usage is 28 bytes}}
+                    // expected-warning@-5 {{Estimated stack usage is 36 bytes}}
+}
+
+// This is only included so recursion is called by the analyzer.
+void call_recursion() {
+  recursion(3);
+} // expected-warning {{Estimated stack usage is 8 bytes}}
+
+void simple_branching() {
+  int A = 1;
+  if (A < 2) {
+    f(A); // expected-warning {{Estimated stack usage is 4 bytes}}
+  } else {
+    //This branch is not executed so we do not get warnings here.
+    f(2 * A);
+  }
+  // We do get the maximal usage calculated with the never executed branch
+  // included.
+} // expected-warning {{Estimated stack usage is 20 bytes}}
+