rasterize's blog

Strange Bug.
By rasterize, history, 9 years ago, In English

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?

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Yes, you are right, it's undefined behavior: non-void function without return(except for main) causes UB

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The return at the end is never called

      You know it, but compiler and optimizer don't

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          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 -O2 flag):

          • 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: if int cannot 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 isInArray became return true and it does not check anything! Why? You cannot return false, because you would have to read tab[4] before — which is what you cannot do! Noticeably, if you change 5 in line 7 to 4, everything works fine).

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Where is the contradiction? In both your examples undefined behavior is reached on some iteration.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                9 years ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                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.

                → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rasterize (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rasterize (previous revision, new revision, compare).

→ Reply