[cfe-dev] -Wunreachable-code and templates

[David Blaikie]

On Thu, Mar 15, 2012 at 5:46 PM, Ted Kremenek <kremenek at apple.com> wrote:
> I think this all looks reasonable, but I suggest we do the CFG changes first that you are proposing for handling 'sizeof' in conditions, as this may impact the results here.

Sure, if you think that's best. I agree it'll be interesting to see
the interaction between these various different parts - and this one
is relatively optional compared to sizeof, macros, etc.

> The performance numbers seem very reasonable for this to be a useful warning, although I still don't think it would be on by default.

-Wunreachable-code certainly isn't up to on-by-default yet, but do you
mean that the template-unreachability would be treated separately/not
on-by-default even once we fix the non-template false positives (like
sizeof) (or a 3rd option - you think unreachable-code overall
(template & non-template) would never be on-by-default for some
reason)?

>  I'm also wondering how much more stuff we can put under -Wall that runs into stylistic preferences, but we can have that debate later.

Unreachable code as a stylistic preference such as the ways you can
have deliberately unreachable code (like the current "if (0)" in
LLVM/Clang code), or something else?

>
> Out of curiosity, I noticed:
>
>> +// FIXME: we should see the next note only 3 times and the following warning once, not twice
>> +//        since it is independent of the template parameter 'I'.
>>  template <int I> struct S {
>> -  char arr[I]; // expected-note 2 {{declared here}}
>> +  char arr[I]; // expected-note 4 {{declared here}}
>>  };
>>  template <int I> void f() {
>>    S<3> s;
>> -  s.arr[4] = 0; // expected-warning {{array index 4 is past the end of the array (which contains 3 elements)}}
>> -  s.arr[I] = 0; // expected-warning {{array index 5 is past the end of the array (which contains 3 elements)}}
>> +  s.arr[4] = 0; // expected-warning 2 {{array index 4 is past the end of the array (which contains 3 elements)}}
>> +  s.arr[I] = 0; // expected-warning {{array index 5 is past the end of the array (which contains 3 elements)}} \
>> +                   expected-warning {{array index 3 is past the end of the array (which contains 3 elements)}}
>>  }
>
> What exactly is going on here?  Is it because the warning is found both in the instantiation and in the uninstantiated template?

That's correct. Once for the pattern, once for each instantiation.

> How do you think we should handle that?

I believe John McCall implied that he & Doug had some ideas about
improving template compile time by not re-processing non-dependent
expressions. That might not apply perfectly to this case, if not we
could just do some other duplicate pruning.

In any case the bug (that non-dependent warnings are duplicated for
every instantiation) already exists and at worst the duplicate from
analyzing the pattern should be just handled by whatever solution we
find to that, but at best, having the 'authoritative' diagnostic in
cases where we can provide it from the diagnostic.

But, curiously, I thought I'd modified the code in my change so that
analyzing the template pattern would only be used for unreachable
code, not the runtime behavior warnings. We should only be flagging
the array index issue for provably reachable code & we can't prove
reachability while looking at the template pattern (just like we can't
prove unreachability by looking at the template instantiation).

Thanks again for your time/thoughts,
- David

>
>
> On Mar 9, 2012, at 9:48 PM, David Blaikie <dblaikie at gmail.com> wrote:
>
>> Ping
>>
>> On Thu, Feb 16, 2012 at 10:41 PM, David Blaikie <dblaikie at gmail.com> wrote:
>>> On Wed, Feb 15, 2012 at 10:34 AM, Ted Kremenek <kremenek at apple.com> wrote:
>>>> On Feb 14, 2012, at 4:35 PM, David Blaikie <dblaikie at gmail.com> wrote:
>>>>
>>>> So I've come up with some numbers for feedback.
>>>>
>>>> Experiment:
>>>> * Take the attached templates.cpp (it includes every C++11 header
>>>> clang can compile (I was using libstdc++ for this), plus a bunch of
>>>> boost headers - and a little hand-written sanity check)
>>>> * preprocess it (with -std=c++11)
>>>> * strip out the line directives (so that clang won't suppress all the
>>>> diagnostics because they're in system headers)
>>>> * using "perf stat -r100":
>>>>  * run with -Wno-everything and either with or without
>>>> -Wunreachable-code -c -std=c++11
>>>>  * run the same thing with the template_unreachable.diff applied
>>>> (I did this at runlevel 1 to try to reduce some of the noise/background)
>>>> This is basically the worst case I can think of - lots of templated
>>>> code, almost no instantiations or non-templated code.
>>>>
>>>> Results
>>>> * you should observe relatively similar results to mine in results.txt
>>>> except:
>>>>  * I pruned the 100 repetitions of diagnostics from the results file,
>>>> leaving only one sample of the diagnostic output from the two
>>>> -Wunreachable-code runs (with & without my patch applied)
>>>>  * I added the check to not build the CFG if we're in a dependent
>>>> context and -Wunreachable-code is /not/ enabled after I'd already run
>>>> my perf numbers, so the discrepency in my results between the two
>>>> versions without the flag enabled should probably not be there (I can
>>>> rerun that to demonstrate if desired)
>>>>
>>>> & these were the execution time results I got:
>>>>
>>>> No patch
>>>>  No warning: 1.915069815 seconds ( +-  0.02% )
>>>>  Warning (10 found): 1.923400323 seconds ( +-  0.02% )
>>>> With patch
>>>>  No warning: 1.937073564 seconds ( +-  0.03% ) (this should probably
>>>> be closer to/the same as the first result - it was just run without
>>>> the shortcut as called out above)
>>>>  Warning (20 found - including my sanity check): 1.980802759 seconds
>>>> ( +-  0.03% )
>>>>
>>>> So about a 3% slow down (in the enabled case), according to this
>>>> experiment which is a pretty extreme case.
>>>>
>>>> What do you reckon? Good? Bad? Need further data/better experiments?
>>>>
>>>>
>>>> Hi David,
>>>>
>>>> Thanks for doing these measurements.  I think we need to do more
>>>> investigation.
>>>>
>>>> If you told me that we have the distinct possibility of incurring a 3%
>>>> compile time regression, I'd say that this warning would *never* be on by
>>>> default.  A 3% regression is *huge* for a single warning.  Your
>>>> measurements, however, are completely biased by your test case.  I think
>>>> this test shows that the analysis doesn't become ridiculously slow in the
>>>> worst case (a good property), but it doesn't tell me what the real
>>>> performance regression is going to be on normal code.  For example, what is
>>>> the build time impact on the LLVM codebase,
>>>
>>> More numbers. I've done 10 builds of LLVM+Clang of each of the 4
>>> variations & come up with the following results:
>>>
>>> 1) Without unreachable template analysis
>>> 1.1) Without -Wunreachable-code: 1924.114592416 seconds ( +-  0.01% )
>>> 1.2) With -Wunreachable-code: 1926.877304953 seconds ( +-  0.01% )
>>> 2) With unreachable template analysis
>>> 2.1) Without -Wunreachable-code: 1925.351616127 seconds ( +-  0.01% )
>>> 2.2) With -Wunreachable-code: 1932.952966490 seconds ( +-  0.00% )
>>>
>>> (& for those running the numbers at home - that's around 21.5 hours ;))
>>>
>>> That's a 0.46% degredation from 1.1 (old code, -Wno-unreachable-code)
>>> to 2.2 (-Wunreachable-code with templates) and a 0.32% degredation
>>> from -Wunreachable-code without templates to with templates.
>>>
>>> Honestly I'm rather surprised perf-stat's reported standard deviation
>>> between builds was as low as it was (I even wrote a silly program to
>>> randomly sleep for 1 second or not sleep - just to see if I could
>>> elicit a high variation number from perf stat - and it did report what
>>> I would expect, roughly, from that - still wish it'd give me the raw
>>> numbers in a more consumable form... but maybe I'll trust it more in
>>> time).
>>>
>>> I can try a Chromium build too, if you like.
>>>
>>> Another thing to consider is that we could put this case under a
>>> sub-flag if we wanted to.
>>>
>>> As for the warnings - examining all of LLVM+Clang the total current
>>> -Wunreachable-code warnings are:
>>> Excluding templates: 1252
>>> Including templates: 1272
>>>
>>> Of the 20 cases found, 4 (in SparseBitVector.h) were false positives
>>> due to sizeof and the other 16 were fairly mundane legitimate cases
>>> due to return/break directly after llvm_unreachable, etc (probably due
>>> to Craig Topper's recent changes from assert(0) -> llvm_unreachable
>>> making more code unreachable. I'll do another pass & checkin fixes to
>>> the legitimate cases (within & outside templates) soon-ish).
>>>
>>> The results.tgz archive contains various details:
>>> results_trimmed.txt - stripped most of the make/build output & the
>>> duplicate batches of diagnostics, so this includes one set of
>>> diagnostics and the perf-stat results for each of the 4 batches.
>>> results_no_templates.txt/results_templates.txt - the diagnostics from
>>> building (once) with -Wunreachable-code with and without my change.
>>> results_no_templates_summary.txt/results_templates_summary.txt - the
>>> sorted & uniqued warning lines from the above - showing the individual
>>> diagnostics that case found (without duplicates either from header
>>> inclusion or from the multiple builds that were run)
>>>
>>> I hope this helps,
>>> - David
>>>
>>>> Chrome, or building code that
>>>> uses Boost?  That's the kind of measurement I think we need to see.  There's
>>>> going to be a lot more variance there, but at the end of the day these
>>>> measurements don't tell me the performance regression I should expect to see
>>>> from this warning.
>>>>
>>>> As for the warnings found, what was the false positive rate?  We're these
>>>> real issues?
>>>>
>>>> Cheers,
>>>> Ted
>> <results.tgz><template_unreachable.diff>
>