using undeclared function returning bool results in wrong return value

[Thanos Makatos via Gcc]

I run into a problem that I'm not sure whether it's a bug in my program (most 
likely) or something wrong with GCC (highly unlikely, I know, hence why I 
haven't sent this to gcc-bugs). The problem is using a function that returns a 
bool, defined in another source file without a declaration, and the program 
compiled with -O. In my test, function foo1 returns true while it should be 
returning false.

Here are the files and repro:

/* main.c */
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>

bool foo2(int);

void main(void) {
        assert(!foo2(0));
        assert(!foo1(0));
}

/* foo.c */
#include <stdbool.h>

bool foo1(int n) {
        return n == 1 || n == 2 || n == 4;
}

bool foo2(int n) {
        return foo1(n);
}

# gcc --version
gcc (Debian 8.3.0-6) 8.3.0
# gcc main.c foo.c -O
In file included from main.c:3:
main.c: In function 'main':
main.c:9:10: warning: implicit declaration of function 'foo1'; did you mean 
'foo2'? [-Wimplicit-function-declaration]
  assert(!foo1(0));
          ^~~~
# ./a.out
a.out: main.c:9: main: Assertion `!foo1(0)' failed.
Aborted

I get the same behavior if I use char instead of bool.

The problem goes away if:
1. I declare foo1 in main.c (just like I do for foo2), or
2. compile w/o -O, or
3. use n == 3 instead of n == 4 in the return statement, or
4. use short or int instead of bool/char.

Am I causing undefined behavior because I'm not declaring foo1?

Please CC me in your response, I'm not subscribed to this list.