[cfe-dev] -Wunreachable-code and templates

[Ted Kremenek]

On Feb 15, 2012, at 11:19 AM, David Blaikie <dblaikie at gmail.com> wrote:

> On Wed, Feb 15, 2012 at 11:12 AM, Ted Kremenek <kremenek at apple.com> wrote:
>> On Feb 15, 2012, at 10:58 AM, David Blaikie <dblaikie at gmail.com> wrote:
>> 
>> Honestly I think there may end up being an argument for this - and
>> using a lesser definition of reachability (the same one MSVC and GCC
>> appear to use - purely structural with no constant conditional
>> evaluation (eg: "if {return} else {return} return" finds the trailing
>> return to be unreachable, but "if {return} return" doesn't, even if
>> the condition on the if is reachable)) under some circumstances (yes -
>> this would cause more false positives on every other analysis-based
>> warning, though I'm curious how much time we spend on CFG construction
>> for all those currently - I might try that as a separate experiment if
>> I can get usable/stable numbers from reasonable data sets).
>> 
>> 
>> Hi David,
>> 
>> I honestly didn't understand this paragraph.  Could you elucidate?
> 
> Sorry - bit rambly/nested.
> 
> GCC and MSVC use a fairly simplistic definition of reachability that
> does not consider conditions at all, eg:
> 
> if (x)
>  return
> else
>  return
> return // unreachable by GCC and MSVC, regardless of 'x'
> 
> if (x)
>  return
> return // reachable by GCC and MSVC, regardless of 'x'
> 
> I'd be interested to see how much faster we could build the CFG if we
> did it in this way - how much we're paying for a stronger definition
> of reachability. I suppose this wouldn't be hard to test - no doubt
> there's some code in the CFG builder that evaluates a condition to
> determine if it's true, false, or unproven & I could just change that
> to always unproven.

I suspect that there isn't any significant cost in the CFG builder to prune branches.  All of the basic blocks are still constructed, and the pruning just involves checking if the condition is a constant expression, which is cheap, and possibly something we can further optimize.  In other words, I believe that 99% of the work of the CFG builder is just visiting all AST nodes and constructing basic blocks, and I believe less than 1% is used pruning branches.

We could base the warning on top of an "unoptimized CFG", but the warning still would require doing what is essentially a DFS of the CFG, so the same time cost is there.  In a previous thread, I discussed the opportunity to potentially record in the CFG what branches we pruned, giving us both the "unoptimized" and "optimized" view of the CFG in one data structure.  Currently clients that want the unoptimized CFG need to separately construct it (we have an API hook for this in AnalysisContext).

If you don't want to take into account branch conditions for reachability, then the only way I see to make this warning super fast is to have the builder record basic blocks in the CFG that have no predecessors because they are trivially dead during CFG construction.  The cases you describe, e.g., the unreachable "return", would fall under this.  Thus you basically do the majority of the work when building up the CFG, and you get an algorithmic win by changing the underlying implementation of the warning.

I suspect that the average cost of this warning is not super high, but it needs to be measured.  There are potentially optimization tricks we can do.  For example, if we know that no branches are dropped from a CFG **and** we know that no basic blocks that are trivially unreachable then we can just skip analyzing a function entirely for the warning (i.e., by definition, everything is reachable).  That could possibly lead to huge performance wins.