Ehren's Blog

A static analysis for fallthrough switch cases in C++

Posted in Seneca by ehren on February 8, 2010

For my 0.5 release in DPS911 I’d like to discuss some work on a Treehydra script for detecting fallthrough cases in a switch statement. I’ve actually been working on this off and on for some time, but it’s only been within the last few hours that I’ve arrived at something airtight.

Actually, I began work on such a script quite a while ago, after completing similar work on finding unreachable blocks in the control flow graph. Most of the serious bugs turned up by this analysis were all caused by forgetting the break statement (see bug 536438 and bug 536646) so a warning/error for this seemed natural. Also, I assumed this would be easy: just find all the basic blocks corresponding to the case labels of the switch and, if the successor of a block corresponds to the next case, you’ve got a fallthrough.

To make this more clear, here’s a simple switch statement that falls through:

int foo(int x) {
  switch(x) {
    case 0:
      x++;
    case 1:
      x--;
  }
}

And here’s a -fdump-tree-all printing of the cfg:

;; Function int foo(int) (_Z3fooi)

int foo(int) (x)
{
  # BLOCK 2
  # PRED: ENTRY (fallthru)
  switch (x)
    {
      case 0: goto <L0>;
      case 1: goto <L1>;
      default : goto <L2>;
    }
  # SUCC: 3 4 5

  # BLOCK 3
  # PRED: 2
<L0>:;
  x = x + 1;
  # SUCC: 4 (fallthru)

  # BLOCK 4
  # PRED: 2 3 (fallthru)
<L1>:;
  x = x + -1;
  # SUCC: 5 (fallthru)

  # BLOCK 5
  # PRED: 2 4 (fallthru)
<L2>:;
  return;
  # SUCC: EXIT
}

Notice something funny? There’s now a default case label! GCC will always insert this dummy default by the time you’ve reached the cfg and, even worse, there’s no way to distinguish a switch statement with a real default from one without, once you’ve reached this level. Unfortunately, I spent a great deal of time trying to do just that, at various times thinking I finally had the solution only to discover a new test case that would totally blow apart the analysis. I think I’ve tried maybe a dozen different approaches only to give up in disgust at various points. See here for one totally invalid early attempt.

So what’s the solution? I needed information from two separate passes of the compiler: The cfg, but also the initial c++ ast representation to find out if the default was really a default. To this end, I knew walk_tree would be needed. I was even able to find a bug in Treehydra during some initial experiments. However, as before, once I thought I had the solution, a more complex test case would ruin everything.

Anyway, here’s the finalish script which also employs a fallthrough() function/annotation to suppress the warnings. Once I’ve had a bit of time to sleep on it, I’m going to refactor a bit and then post to the bug. I also need to consider how to integrate this into a –with-static-checking build. There are a number of issues I had to take into account that I haven’t mentioned, as well, such as when the order of the cases is mixed up (eg case 1 before case 0) and also when labels and gotos come into the mix. (Properly dealing with switches embedded within switches … was the last hurdle.)

For a demonstration, here’s a nasty bit of code together with a sample run of the script.

So, for my 0.6 release, I’ll have to get back to dead code, hopefully being able to exploit callgraph to the fullest. Perhaps I can find another analysis to start work on as well.

Advertisements

One Response

Subscribe to comments with RSS.

  1. pokemon go hack said, on November 27, 2016 at 7:02 pm

    Have ʏou eѵer consifered аbout adding a littlе biit mоге thɑn ust
    ʏoᥙr articles? I mean, what you saay іs fundamental аnd аll.

    Neѵertheless tɦink about if you аdded sme great photos
    oг vireo clips tߋ givve yor posts mօre, “pop”!
    Yоur cⲟntent iss excellent Ьut with images ɑnd videos, this blog сould
    сertainly bе one ߋf the greeatest in its niche.
    Terrific blog!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: