I don't think the network in this case was generated by an algorithm. According to Knuth, this network was discovered by M. W. Green and it's still the smallest (60 comparators) 16-input network known.
It's because of the difference in how arguments are passed to functions in 32-bit vs 64-bit mode.
In the System V AMD64 ABI, the first integer argument to a function is passed in the rdi register.
The fib function however, being written for 32-bit mode, is expecting the argument on the stack, and loads it from esp+4, so it gets a garbage value.
The value on the top of the stack is the return address, which is probably somewhere around 0x0000000000400000 (the default entry point). Loading from esp+4 gets the high bits which are all zeros, so that's what goes into %ecx.
If you build the program as a position-independent executable (gcc -fpic -pie), it will get loaded at a random address and it will print a different value.