Last Comment Bug 535646 - Static analysis to warn/error on unreachable basic blocks in the CFG
: Static analysis to warn/error on unreachable basic blocks in the CFG
Status: NEW
:
Product: Core
Classification: Components
Component: Rewriting and Analysis (show other bugs)
: unspecified
: x86 Linux
: -- enhancement with 1 vote (vote)
: ---
Assigned To: Ehren Metcalfe
:
Mentors:
Depends on: 536412 536438 536627 536646 536651
Blocks: analyses
  Show dependency treegraph
 
Reported: 2009-12-17 13:23 PST by Chris Jones [:cjones] inactive; ni?/f?/r? if you need me
Modified: 2011-02-09 08:43 PST (History)
10 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
invalid analysis (1.09 KB, text/plain)
2009-12-18 19:57 PST, Ehren Metcalfe
no flags Details
working analysis (974 bytes, text/plain)
2009-12-22 00:43 PST, Ehren Metcalfe
no flags Details
analysis results (171.65 KB, text/plain)
2009-12-22 01:40 PST, Ehren Metcalfe
no flags Details
working analysis (847 bytes, application/javascript)
2009-12-22 12:08 PST, Ehren Metcalfe
no flags Details

Description Chris Jones [:cjones] inactive; ni?/f?/r? if you need me 2009-12-17 13:23:30 PST
Bug 535298 ended up reducing to this problem

int foo() {
    int x = 1;
    ++x;
    return x;
    --x;
}

where |--x| was important.  This was not caught because gcc doesn't warn on this condition.

Note that this analysis is much easier than a general "dead code" analysis: literally, a treehydra script would just need to check the reachability of CFG nodes to catch this stupid error.  No values need to be tracked.
Comment 1 Chris Jones [:cjones] inactive; ni?/f?/r? if you need me 2009-12-17 13:25:02 PST
Sorry, that was bug 535321 (I think).
Comment 2 Chris Jones [:cjones] inactive; ni?/f?/r? if you need me 2009-12-17 13:27:13 PST
Nope.  I'm going to stop trying to link back.
Comment 3 Ehren Metcalfe 2009-12-18 19:57:29 PST
Created attachment 418468 [details]
invalid analysis

I attempted to write the "obvious" analysis for this (attached). I think there might not be an easy way to do this with treehydra though. 

Here's why: After building the cfg, if gcc recognizes an unreachable block it immediately runs pass_cleanup_cfg (via TODO_update_cfg) which deletes the block. This happens before the treehydra "after_gcc_pass: cfg" can run (so it only sees the reachable blocks).

I could be totally off track here though.
Comment 4 Ehren Metcalfe 2009-12-22 00:43:53 PST
Created attachment 418799 [details]
working analysis

Here's an updated analysis (the original didn't consider that a block's successor might be a predecessor eg with a loop).

I ended up patching gcc to remove the TODO_update_cfg flag which allows this to work. For good measure I made sure that pass_cleanup_cfg runs after pass_build_cfg in every case. (I can post a patch if anyone's interested).
Comment 5 Ehren Metcalfe 2009-12-22 01:40:10 PST
Created attachment 418807 [details]
analysis results

Here's 922 unreachable blocks caught by the analysis. Most of these are pretty boring (redundant return statements after switch statements etc) but there are some funny ones.

eg:

this file's full of "double returns": http://hg.mozilla.org/mozilla-central/file/5803dc30baea/content/canvas/src/WebGLContextGL.cpp#l2973

this ifdef could be wrong: http://hg.mozilla.org/mozilla-central/file/5803dc30baea/widget/src/gtk2/nsWindow.cpp#l2020

redundant return: http://hg.mozilla.org/mozilla-central/file/5803dc30baea/content/html/content/src/nsGenericHTMLElement.cpp#l2907

this lazy-or return could be a mistake: http://hg.mozilla.org/mozilla-central/file/5803dc30baea/layout/mathml/nsMathMLChar.cpp#l724

(So far I've only gone through these at random)
Comment 6 Ehren Metcalfe 2009-12-22 01:52:42 PST
oops. the problem with that last one isn't the return. It's that the switch doesn't have any break statements: http://hg.mozilla.org/mozilla-central/file/5803dc30baea/layout/mathml/nsMathMLChar.cpp#l698

That can't be right?
Comment 7 Chris Jones [:cjones] inactive; ni?/f?/r? if you need me 2009-12-22 09:54:49 PST
Good stuff!  You should start filing these, some look bad.
Comment 8 Ehren Metcalfe 2009-12-22 12:08:12 PST
Created attachment 418886 [details]
working analysis

There was an efficiency nit with the old script that was really bugging me.

btw, the ifdef thing above is not a bug.
Comment 9 mozilla 2011-02-09 08:43:36 PST
note that gcc has warnings for unreachable code, possibly introduced since this bug was filed, enabled with the -Wunreachable-code option

Note You need to log in before you can comment on or make changes to this bug.