The Curious Case of the Disappearing “if”
Tags: c, cpp, debugging
Published: 2022-06-20 23:48:07

---
title: The Curious Case of the Disappearing “if”
published: true
description: How an uninitialized but unused argument resulted in a crash.
tags: #c #cpp #debugging
---

## Introduction

I recently discovered a test-case that crashed [`cdecl`](https://github.com/paul-j-lucas/cdecl):

```txt
c++decl> explain int operator new(size_t)
Assertion failed: (ast != NULL), function c_ast_unpointer_qual, file c_ast_util.c, line 404.
zsh: abort (core dumped)  c++decl
```

> FYI, it’s a negative test: operator `new` _must_ return `void*`, not `int`.
>
> Briefly, `cdecl` is a program that helps you compose and decipher C (or C++) declarations or casts.  Its parser parses C (or C++) declarations and constructs an [abstract syntax tree](https://en.wikipedia.org/wiki/Abstract_syntax_tree) (AST) that is then traversed to check for semantic errors.

The crash is strange for a couple of reasons that I knew initially.  The test:

1. Crashes only when `cdecl` is compiled using clang 14.0.5.
2. Does _not_ crash when compiled with various versions of `gcc` on any platform.

(I’d come to discover that it’s even stranger later.)

## The Code

Here’s the code of the function containing line 404:

```c
static c_ast_t const* c_ast_unpointer_qual( c_ast_t const *ast,
                                            c_tid_t *qual_stids ) {
  ast = c_ast_untypedef( ast );
  if ( ast->kind != K_POINTER )
    return NULL;

  ast = ast->as.ptr_ref.to_ast;
  assert( ast != NULL );         // <-- Line 404: THIS FAILS
  assert( qual_stids != NULL );
  *qual_stids = ast->type.stids & TS_ANY_QUALIFIER;
  // ...
  return c_ast_untypedef( ast );
}
```

> This function takes pointer to an AST node and, if it represents a pointer in a C declaration, “un-pointers” it to obtain the pointed-to AST node.  It also gets the qualifiers, e.g., `const`, of the pointed-to AST node.

Specifically, the first `assert()` fails which means `ast` is `NULL` which means `as.ptr_ref.to_ast` is `NULL`.  That means `to_ast` wasn’t set when the AST was being constructed in the parser — or so I thought.

## Using a Debugger

The first thing I did was try to use a debugger and set a breakpoint a few lines up.  Unfortunately, the line I wanted to set the breakpoint on was eliminated by the compiler.  So I set a breakpoint nearby.  Unfortunately again, the value of `ast` had been “optimized out” by the compiler.

So I recompiled with `-O0` — but then the program _didn’t_ crash.  A [Heisenbug](https://en.wikipedia.org/wiki/Heisenbug)! (This _isn’t_ a good sign.)  So I set a breakpoint in the function that calls `c_ast_unpointer_qual()` (which I learned from the backtrace from the core dump):

```c
c_ast_t const* c_ast_is_ptr_to_tid_any( c_ast_t const *ast,
                                        c_tid_t tids ) {
  c_tid_t qual_stids;
  ast = c_ast_unpointer_qual( ast, &qual_stids );
  return c_ast_is_tid_any_qual_impl( ast, tids, qual_stids );
}
```

> This function takes a pointer to an AST node and returns the pointed-to AST node, but only if the first represents a pointer _and_ it’s a pointer to any one of a set of types, e.g., `void*`.

This time, the debugger stopped at the breakpoint and I discovered that the AST node represents the built-in type (`K_BUILTIN`) of `int` (the declared return type of operator `new`) and in particular it’s _not_ `K_POINTER`.  That means this `if`:

```c
  if ( ast->kind != K_POINTER )
    return NULL;
```

should have evaluated to `true`, the function should have returned `NULL`, and, most importantly, should _not_ have even executed line 404.  It’s as if the `if` disappeared. (This _isn’t_ a good sign either.)

## Memory Checkers & Sanitizers

My next step was to try [Valgrind](https://valgrind.org) — nothing useful.  I also tried [address](https://clang.llvm.org/docs/AddressSanitizer.html) and [undefined behavior](https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html) sanitizers — also nothing useful.  Now what?

## Older clang Versions

This test-case didn’t used to crash using `clang`.  (The problem is that, while I do run my full suite of unit tests using `gcc` every time I change the source code, I don’t also do it every time using `clang`.)  So I started downloading older and older versions of `clang` and trying them out.  I finally found out that the crash _didn’t_ happen using `clang` 13.0.1 and started happening using clang 14.0.0.  Although highly unlikely in a program as mature as `clang`, it _is_ possible that I found an optimizer bug.

## Viewing the Object Code

So then I thought to look at the generated assembly code using `objdump` (line split for clarity):
```bash
$ objdump -gSMintel --no-show-raw-insn --symbolize-operands \
  c_ast_util.o > c_ast_util-13.0.1.s
```

Looking at the output for `c_ast_is_ptr_to_tid_any()`, I discovered that the compiler inlined the call to `c_ast_unpointer_qual()`, but that the `if` was there:

```txt
;     if ( ast->kind != K_POINTER )
     ec6:       cmp     eax, 256
     ecb:       jne      <L3>
```

I then recompiled using `clang` 14.0.0 and dumped `c_ast_util.o` again: this time, that `if` was _not_ there!  The likelihood that I found an optimizer bug increased.

## Un-Inlining

The next thing I tried was annotating the function with `__attribute__((noinline))` to force `clang` _not_ to inline the function.  That _worked_!  The likelihood that I found an optimizer bug increased again.

## Static Analysis

I had actually started to file a bug against `clang` when I stumbled across [`scan-build`](https://clang-analyzer.llvm.org/scan-build.html) and tried it.  It flagged [undefined behavior](https://dev.to/pauljlucas/undefined-behavior-in-c-and-c-3a20) in `c_ast_is_ptr_to_tid_any()` (code repeated here):

```c
c_ast_t const* c_ast_is_ptr_to_tid_any( c_ast_t const *ast,
                                        c_tid_t tids ) {
  c_tid_t qual_stids;
  ast = c_ast_unpointer_qual( ast, &qual_stids );
  return c_ast_is_tid_any_qual_impl( ast, tids, qual_stids );
}
```

Specifically, `qual_stids` can be passed uninitialized as an argument to `c_ast_is_tid_any_qual_impl()` since `c_ast_unpointer_qual()` doesn’t _always_ set it.  However, I didn’t think it mattered because:

1. The only way `qual_stids` remains uninitialized is if `c_ast_unpointer_qual()` returns `NULL`; and:
2. The code for `c_ast_is_tid_any_qual_impl()` (below) does nothing if `ast` is `NULL` — specifically, it does _not_ use (the uninitialized) `qual_stids`.

```c
static c_ast_t const* c_ast_is_tid_any_qual_impl( c_ast_t const *ast,
                                                  c_tid_t tids,
                                                  c_tid_t qual_stids ) {
  if ( ast != NULL ) {
    c_tid_t ast_tids = c_type_get_tid( &ast->type, tids );
    ast_tids = c_tid_normalize( ast_tids );
    if ( c_tid_tpid( tids ) == C_TPID_STORE )
      ast_tids |= qual_stids;
    if ( c_tid_is_any( ast_tids, tids ) )
      return ast;
  }
  return NULL;
}
```

So what harm can there possibly be that `qual_stids` is uninitialized?  In fact, since it’s not used in the `NULL` case, _how_ is that even undefined behavior?  The problem is merely _passing_ `qual_stids` to a function means it has to be _read_ and, according to the C11 standard §6.3.2.1¶2, is undefined behavior:

> If the lvalue designates an object of automatic storage duration ... and that object is uninitialized (not declared with an initializer and no assignment to it has been performed prior to use), the behavior is undefined.

And [with undefined behavior, anything is possible](https://raphlinus.github.io/programming/rust/2018/08/17/undefined-behavior.html).  But does it actually matter in _this_ case?

## The Fix

Assuming the undefined behavior is responsible for the `if` disappearing, the fix is trivial: initialize `qual_stids`:

```c
c_ast_t const* c_ast_is_ptr_to_tid_any( c_ast_t const *ast,
                                        c_tid_t tids ) {
  c_tid_t qual_stids = TS_NONE;  // <-- INITIALIZED NOW
  ast = c_ast_unpointer_qual( ast, &qual_stids );
  return c_ast_is_tid_any_qual_impl( ast, tids, qual_stids );
}
```

Compiling with `clang` 14.0.0 and running resulted in `cdecl` _not_ crashing and the test passing!

## Conclusion

Bugs as a result of [undefined behavior](https://dev.to/pauljlucas/undefined-behavior-in-c-and-c-3a20) can be _bizarre_ and make seemingly impossible things happen.  Try every debugging tool at your disposal:

+ [Valgrind](https://valgrind.org) — with the caveat that it works only on generated machine code, not optimized-out code.
+ clang’s [address](https://clang.llvm.org/docs/AddressSanitizer.html) and [undefined behavior](https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html) sanitizers.
+ clang’s [`scan-build`](https://clang-analyzer.llvm.org/scan-build.html).

If something apparently impossible is happening, look at the generated assembly code. For example, when single-stepping in a debugger, if the next line of code you step to isn’t where you think it should be, it’s a hint that the compiler did something unexpected and the assembly code isn’t what you think it is.

## Epilogue

It’s still not clear to me how merely reading but not otherwise using an uninitialized variable resulted in `clang` eliminating the relevant `if`.  But I can’t file a bug against `clang` if my code has undefined behavior since it then becomes permissible to do _anything_.

Why didn’t the [undefined behavior](https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html) sanitizer flag the bug?  My guess is that the undefined behavior is static in nature (thus altered the generated code) whereas the sanitizer checks a running program for _dynamic_ undefined behavior, e.g., integer overflow.