sizeof conditions and -Wunreachable-code

[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.

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? 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)

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?

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 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). 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?).

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 (

) & just provide the (possibly stateful) predicate. This could be
reused for specific_*_iterators in Clang, too)
* Oh - another thing: why are there edges to null in the CFG? Do they
serve a purpose?

unreachable_sizeof.diff (23.4 KB)

Ping

unreachable_sizeof.diff (29.5 KB)

Ping.

unreachable_sizeof.diff (23.5 KB)

Thanks for your patience David. Comments inline.

[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?

Thanks for your patience David. Comments inline.

[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.

Yep, that's what I meant - sorry it wasn't more clear.

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.

Right - the way I put it/think about it: those 'runtime behavior'
warnings are interested in provably reachable code. -Wunreachable-code
is interested in provably unreachable code. Without this change all
blocks fall into one category or the other - with it, we introduce a
3rd type of code: neither proven reachable nor proven unreachable.

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.

I'm happy to do this - I was erring on the side of not so as to keep
space usage down (with only one bit it's easy(ish) to squirrel it away
in the low bit of the edge pointer) & I couldn't think of any client
that would care about sizeof but not dependent or macro, etc. Do you
have any particular clients in mind that might need to differentiate
between these different cases? I don't mind aiming for the more
expressive API from the start if it's what you think is best.

This means that instead of an "Optimistic" argument (which is content free in its name),

Right - like I said, bit of a loss for names in this change.

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).

Right.

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").

Right, sounds good (though, to be clear, this optimization you're
referring to is expressed by the "setAlwaysAdd" function in
CFGBuildOptions? An optimized CFG being one without all edges being
always-add?)

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.

Hmm, still not sure here - it seems like the EH CFG would be a
superset of the non-EH one, but I'll take your word for it at this
point. I suppose it could mean that non-EH client see two blocks where
they would've otherwise seen one, but I'm not sure if that would
adversely impact them.

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.

Yep, sure thing.

(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.

Yeah, this was me being confused - I didn't realize stop to realize
that the "setAllAlwaysAdd" option around AnalysisBasedWarnings:cpp:850
is a superset of the else clause around there - so it's just a matter
of building the least expensive necessary for the required
functionality (& reachable warnings require less than unreachable
ones)

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".

I suspect the base CFG would only need to provide the raw_iterator
(exposing the edge flags) & then all clients would use a virtual CFG -
which could just be template/compile-time polymorphic. A trivial
client providing an all-0 mask could be used by default.

But yeah, that (whether clients ever use the CFG directly, or just the
CFG views) is a minor implementation detail.

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.

I believe for the existing specific_*_iterators a filter_iterator
should be a drop in replacement with little, if any, perf implications
- just a generalizing refactor. But I've got to work on improving the
llvm test-suite & perf results anyway, so I'll be working on it anyway
to try to make it more convenient.

* 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.

I see, makes sense.

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.

Certainly the current state isn't really ship-ready/clean/tidy. I
mostly wanted to check I was on the right track (naming, one flag or a
bit field of edge properties were probably the two big things) & then
there's a fair bit of tidying up to do, certainly.

I'll spend some time thinking about the readability/simplicity of the
CFG API - I've been rather laser focused on the mechanics of these
changes & haven't really given the design a great deal of thought as
yet.

Perhaps it would be best to introduce a filtered_iterator class somewhere that CFG.h would be the primary (initial) client.

Sure thing.

(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).

Yep. I've got some work to do in tidying up the test-suite & making
for a more convenient perf gathering workflow anyway so hopefully
that'll dovetail well with analyzing this work.

What do you think?

Sounds reasonable.

Thanks for your time/input,
- David