title: Undefined behaviour or gcc optimization bug
body: <p><strong>The question is did we introduce undefined behaviour that trips optimizer, or can we file a bug report against gcc?</strong></p>
  
  <p>Sorry for lack of better title, but it's quite fragile and we are almost sure that this is a bug. The minimal example is not our favourite design but it's based on production code that crashed:</p>
  
  <pre><code>#include &lt;iostream&gt;
  
  struct Node
  {
      Node(Node* parent) {
          if(parent) {
             parent-&gt;child_ = this;
          }
      }
      Node* child()
      {
          return child_;
      }
      Node* child_ = nullptr;
  };
  
  void walk(Node* module, int cleanup) {
      if(module != nullptr) {
          if(!cleanup) {
              std::cerr &lt;&lt; "No cleanup";
          }
          walk(module-&gt;child(), cleanup);
          if(cleanup) {
              delete module;
          }
      }
  }
  
  int main (){
      Node* top = new Node(nullptr);
      Node* child = new Node(top);
      walk(top,1);
  }
  </code></pre>
  
  <p>Compiled with <code>-O1 -foptimize-sibling-calls -ftree-vrp</code>. Godbolt example: <a href="https://gcc.godbolt.org/z/4VijKb" rel="noreferrer">https://gcc.godbolt.org/z/4VijKb</a></p>
  
  <p>Program crashes calling <code>module-&gt;child()</code> when module is <code>0x0</code>. Inspecting assembler we noticed that <code>if (module != nullptr)</code> is skipped at the beginning of <code>walk</code>. There is a check for <code>cleanup</code> and call to <code>work</code> seems to be unconditional, which results in trying to pull <code>child_</code> from an invalid pointer.</p>
  
  <p>The check is reestablished in assembly (and code seems to work) if:</p>
  
  <ol>
  <li>Any of the two optimizations over <code>-O1</code> is taken away.</li>
  <li>Body of <code>if(!cleanup)</code> is removed. (No side effect from <code>cerr</code>)</li>
  <li>Body of <code>if(cleanup)</code> is removed. (Memory leak, but I think it counts as observable behaviour change)</li>
  <li><code>walk</code> is called before "No cleanup" <code>if</code>. (Operation order)</li>
  <li><code>cleanup</code> type is changed to <code>bool</code> from an <code>int</code>. (Type change - but no observable behaviour change, I think).</li>
  <li>Insertion of unconditional <code>cerr &lt;&lt; "text";</code> before and <code>if(!cleanup)</code>. (Also an observable change.)</li>
  </ol>
  
  <p>It seems like a weird combination of tail-recursion and <code>nullptr</code> check removal that resulted in wrong code. Possibly <code>walk</code> got split into sibling functions based on <code>cleanup</code> checks and got stitched wrongly(?).</p>
  
  <p>Two candidates for UB were:</p>
  
  <ol>
  <li>Hinting compiler that <code>module</code> is non-<code>nullptr</code>, but I don't see a way compiler could infer the result.</li>
  <li>Using <code>int</code> in <code>bool</code> context, but it's legal AFAIK.</li>
  </ol>
  
  <p>FWIW <code>clang</code> seems to produce correct run-time, <code>gcc 8.3</code> also has the assembly for the check present. <code>9.1</code> and <code>trunk</code> not. We don't have any gcc expert at hand, so we had no idea why optimizer could be misled.</p>