[cfe-dev] sizeof conditions and -Wunreachable-code

[Ted Kremenek]

Thanks for your patience David.  Comments inline.

On Feb 21, 2012, at 9:55 PM, David Blaikie <dblaikie at gmail.com> wrote:

> [while the unreachable-code-on-templates analysis/discussion
> continues, I thought I'd take the time to start on perhaps a less
> contentious/more actionable related area. No rush, though - I'll leave
> this here & maybe work on something for Lang to review in the mean
> time]
> 
> One of the major remaining sources of false positives for
> -Wunreachable-code in LLVM/Clang is use of sizeof, mostly in
> BitVector.h:
> 
> if (sizeof(BitWord) == 4)
>  ...
> else if (sizeof(BitWord) == 8)
>  ...
> 
> One of these cases will always produce an unreachable code warning
> from Clang. That's not very helpful.

Very true.  From the results you've provided from analyzing the LLVM codebase, this appears to be a major source of false positives.

> 
> So in the interests of removing these false positives I've worked up a
> first pass of modifications to the CFG (& related bits & pieces) to
> work as follows:
> 
> 1) Track any constant expression evaluation that depended on sizeof evaluation
> 2) Add support for an extra bit flag on CFG edges
> 3) Raise that flag for any edge that depends on a sizeof-dependent
> expression (currently I'm only doing this for sizeof in a switch
> expression - it was slightly less intrusive to plumb this through than
> for the boolean conditions in if/while/etc)
> 4) Filter out these extra edges when iterating over successors and
> predecessors normally
> 5) Include these edges when finding unreachable blocks
> 6) (exclude these edges when we're just doing reachability for things
> like missing returns)
> 
> Ted - do you think this is at least on the right track?

To make (5) and (6) a bit stronger, I'd say:

  - Include these edges only when finding unreachable blocks for -Wunreachable-code

To my mind, all other analyses we have that care about reachability want to prune out these edges, like we are doing now.  This includes diagnostics pruned by using DiagRuntimeBehavior.

Put another way, most analyses want to know if something is unreachable given the current compilation context (compiler options, etc.).  -Wunreachable-code wants to prove that something is ALWAYS unreachable, and thus allows more to be reachable in the CFG so that it isn't overly optimistic.

> Did you have
> some other ideas in mind about how this could be done? (for example -
> I chose to put all these edges in the same list & filter at iteration
> time because I assumed order of edges was important & this way order
> of both edge traversals (with & without the extra edges) remains the
> same as it was before - if order is not important we could simply
> store the extra edges in a separate list & be slightly more efficient
> at iteration rather than having to filter all the time)

Order is very important, so having the filtration be lazy at iteration time seems like the right approach to me.

> Obviously it'll need a fair bit of massaging to get it to a more
> usable state - I couldn't decide what to call the extra
> flags/variables, some are named things like "MayVaryByBuild" (eg: this
> edge may exist or not exist depending on the arch of the build) or
> "Optimistic" (be optimistic about reachability - finding more things
> that can be reached than is strictly true for this build (by
> considering MayVaryByBuild edges)). Perhaps there are some more
> canonical terms that should be applied?

I'd consider breaking it down into specific options, and not lump it under a single flag.  For example, instead of a single MayVaryByBuild, consider an object with a set of bitfields that records the stuff we care about, e.g.:

- was the condition evaluated from a macro?
- did the condition contain a sizeof?
- did the condition contain a dependent expressions?

and so on.  We can then have simple predicate methods that bake these down to higher-level queries, but we don't get an abstraction leak and we can extend "interesting" over time without changing the API.

This means that instead of an "Optimistic" argument (which is content free in its name), one just provides a mask of pruned edges to include, with the default mask being to not include any pruned edge (or "ghost edge" as I have referred to in previous emails).

> 
> Should this be generalized to handle many more flags for different
> kinds of graph edges? I know you mentioned previously that there's
> already one CFG parameter about whether certain edges are included
> ("AllAlwaysAdd"). Are there clients that would benefit from being able
> to build both those graphs in one pass & filter on iteration instead
> of requesting multiple builds of the CFG?

It's a good question.  I think there is general value in being able to describe the attributes of an edge (e.g., macros, sizeof, etc., as I mentioned above), but it gets more complicated.  Currently we provide an "unoptimized CFG" and a "CFG with exceptions" as two alternative CFGs that can be constructed.  We also allow the CFG to be linearized (or not), but that's an entirely different topic that is unrelated.

For the "unoptimized CFG", it's just the CFG before you prune out edges.  It takes basically the same amount of work to build, except that we don't drop edges.  If we can categorize pruned edges instead of dropping them, then clients who want the "unoptimized CFG" can just iterate over all the edges instead of implicitly skipping over the ones we think that most clients won't want to see (i.e., the ones in the "optimized CFG").

The CFG with exceptions is a different issue.  It requires more work to build, generates a lot more edges, and may cause the *structure* of the CFG to be different.  It's not just about pruning edges; we may have additional basic blocks, etc, to represent EH logic.  For that case, I think it still makes sense to allow one to build a CFG with slightly different build options, instead of having a single (overly complex) CFG to rule them all.

The current interface to the CFG is fairly simple, and I'd like to keep it simple for 99% of the clients.  -Wunreachable-code is a client that wants a bit more functionality from the CFG, so I think it is fine for it to use the more complicated CFG iterators that allow one to see more of the edges.

> (it doesn't look like
> AnalysisBasedWarnings needs to build two CFGs just because it
> sometimes needs the "AllAlwaysAdd" flag - so I guess both kinds of
> clients can use the more expensive CFG, so this question is probably
> irrelevant).

That's a bit different.  The issue there is whether or not we should always be linearizing the CFG.  That's the approach we've taken with the static analyzer, since that is a client that wants to see *every* expression.  What you are seeing in AnalysisBasedWarnings.cpp is an approximation to that.  The regular CFG doesn't linearize the entire AST into the CFG, but instead encodes the most important control-dependencies with the minimal number of elements in the CFGBlocks.  The 'AllwaysAddFlag' allows us to tell the CFGBuilder to always include specific kinds of expressions in the CFG because they are consumed by various analysis (e.g., -Wuninitialized).  This is a hack.  It allows logic for -Wuninitialized to just scan the CFG, instead of walking the AST.

I also don't know why you think two CFGs are constructed.  As far as I can tell, the AlwaysAddFlags are specified up front, and then any consumer of the CFG lazily gets a CFG from the AnalysisContext with those settings.

> But if extra flags are needed we could generalize this
> better with some kind of flag mask for construction and then a flag
> mask & value to filter on when iterating over edges (or an entire
> filtered view of the CFG?).

That's one option.  You could also layer a "virtual CFG" on top of a real one, and have its iterators just provide the filtration implicitly.  The virtual CFG wouldn't result in the construction of a new CFG.  Instead it would have a CFG* to a real CFG, and then implement its own iterators that filtered on the edges.  The base CFG could then provide a "raw_iterator" or a "filtered_iterator" and a normal "iterator".

> A couple of asides:
> 
> * I found a bug in the FilteredCFGBlockIterator - it doesn't filter on
> the first element (fix is included/necessary for my patch).
> * FilteredCFGBlockIterator could probably be refactored out to a more
> general device like a filtering iterator (
> http://blogs.msdn.com/b/vcblog/archive/2010/08/09/the-filterator.aspx
> ) & just provide the (possibly stateful) predicate. This could be
> reused for specific_*_iterators in Clang, too)

That might be very useful.  As you observe, we use filtered iterators already in Clang, with a good example being specific_decl_iterator, defined in DeclBase.h.  I think the rollout out would be to try it out first, see if we can refactor it, measure the performance implications, and see how widely applicable we can make it.

> * Oh - another thing: why are there edges to null in the CFG? Do they
> serve a purpose?

Definitely.  The CFG has invariants on its structure.  For example, a block terminated with an 'if' always has two successors, and the order of successors matters.  Clients expect this, because the edges are not labeled (e.g., "which is the true branch?").  If an edge is infeasible, it gets pruned out by being set to null.

In general, I think this is on the right track.  I have two concerns:

(a) After we make these changes, I still want CFG.h to be very readable.  Perhaps it would be best to introduce a filtered_iterator class somewhere that CFG.h would be the primary (initial) client.

(b) Performance.  Will the filtered iterators introduce a performance problem?  My guess is no.  When one traverses over the CFG, there is a lot of other work done by the clients (e.g., their analysis logic) that dominates the actual iterating over successors and predecessors.  Filtered iterators, however, introduce new conditional logic, so we'll want to measure the performance impact (which we expect to be negligible).

What do you think?