Hello, I encountered a strange bug while solving POJ 3278 .
here's my AC solution: http://ideone.com/FdyTlU
Strangely if I submit my solution using G++ and remove the 38th line I get a WA verdict.
Now I tried using random other values instead of -1 to see if it mattered and strangely it doesn't. As long as I return something I pass the tests, it doesn't matter what I return, So I don't really see the point of the line if it's essentially just unreachable code.
SIDE NOTE: Submitting the solution using C++ passes the tests which makes the situation even more confusing.
Is there something related to the compilers that's causing this? Or did I somehow invoke undefined behavior?
Yes, you are right, it's undefined behavior: non-void function without return(except for main) causes UB
I see. So it's Undefined behaviour even if the function always returns a valid answer? The return at the end is never called or used as is evident, since changing the return value doesn't affect the answer.
The return at the end is never called
You know it, but compiler and optimizer don't
Undefined behavior only appears if the corresponding place is reached by the program. If you don't reach the UB location, you also don't trigger UB.
Not true. Compiler can assume that undefined behavior never happens and optimize some parts of the code. Some examples that blew my mind one day (they work for sure in recent
gccs with-O2flag):Signed integers should not overflow: http://ideone.com/WJgUNK (if you see in assembler code, you'll realize that it's become the
while (true)loop: ifintcannot overflow, how could it become negative?)You should not read/write out of array: http://ideone.com/BWCcMT (you will see in assembler dump that whole function
isInArraybecamereturn trueand it does not check anything! Why? You cannot return false, because you would have to readtab[4]before — which is what you cannot do! Noticeably, if you change5in line 7 to4, everything works fine).Where is the contradiction? In both your examples undefined behavior is reached on some iteration.
Look at the second example. Undefined behavior is never reached during the runtime! The function is optimized into
return true, which is a really good function which never hits undefined behavior.I just wanted to show that UB may change also the behavior of the compiler, not only the compiled program. It may generate some correct code, not having UB anymore, but possibly doing not what you want. But you're partially right that UB would happen if compiler did nothing about this.
Now I see your confusion. Undefined behavior does not need to be reached strictly at run time. It is enough that it would be reached conceptually, by executing the program on an abstract machine.
In both your examples, UB is reached conceptually, and the result is "undefined", which here takes the form of incorrect optimizations. You can't really say that the resulting code does not have UB — the whole produced program is the result of UB, and its contents are irrelevant.
EDIT: To be more precise, the produced program would only behave correctly up to the first place where UB would be reached.
Auto comment: topic has been updated by rasterize (previous revision, new revision, compare).
Auto comment: topic has been updated by rasterize (previous revision, new revision, compare).