Static analysis to warn/error on unreachable basic blocks in the CFG

NEW
Assigned to

Status

()

Core
Rewriting and Analysis
--
enhancement
8 years ago
6 years ago

People

(Reporter: cjones, Assigned: Ehren Metcalfe)

Tracking

(Blocks: 1 bug)

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments, 2 obsolete attachments)

171.65 KB, text/plain
Details
847 bytes, application/javascript
Details
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.
Sorry, that was bug 535321 (I think).
Nope.  I'm going to stop trying to link back.
(Assignee)

Comment 3

8 years ago
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.
(Assignee)

Comment 4

7 years ago
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).
Attachment #418468 - Attachment is obsolete: true
(Assignee)

Comment 5

7 years ago
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)
(Assignee)

Comment 6

7 years ago
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?
Good stuff!  You should start filing these, some look bad.
(Assignee)

Updated

7 years ago
Depends on: 536412
(Assignee)

Updated

7 years ago
Depends on: 536438
(Assignee)

Comment 8

7 years ago
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.
Attachment #418799 - Attachment is obsolete: true
(Assignee)

Updated

7 years ago
Assignee: nobody → ehren.m
Depends on: 536627
(Assignee)

Updated

7 years ago
Depends on: 536646
(Assignee)

Updated

7 years ago
Depends on: 536651

Comment 9

6 years ago
note that gcc has warnings for unreachable code, possibly introduced since this bug was filed, enabled with the -Wunreachable-code option
You need to log in before you can comment on or make changes to this bug.