Change in optimisation with UB in mind

With LLVM v5.0, I found failures in some of the ‘gcc.c-torture/execute’ tests due to a change in the optimisation where undefined behaviour is involved. The tests that fail are the ‘20040409-[123].c’ tests.

The underlying failure is due to the optimisation of the following:

int test2(int x) { return x + INT_MIN; }

from using an ADD instruction to using an OR instruction. The optimisation is entirely valid and will produce the correct result for all correct values of ‘x’, but it introduces a change for architectures that have support for detecting integer overflow/underflow (signalling or quiet).

For many systems the execution cost of ADD versus OR is the same, so there is no real reason to choose one versus the other, and UB is UB either way. However, it does impact detection of out-of-range integer arithmetic for systems that have support for this.

Is there a new trait in the TTI, or a call-back elsewhere that allows the target to choose whether it wants this optimisation to use an ADD or an OR (possibly in the cost-models)? I would generally prefer to use ADD versus OR if the cost of execution is the same.

Thanks,

MartinO

It isn't just about execution on the target machine -- transforming
the Add to an Or makes it easier to infer that the highest bit of the
result is always set later in the optimization pipeline. Are the
failing tests unit tests for a C compiler? If so, I'd say the test
cases are broken, unless they're specifically test that e.g. the
compiler does not crash when compiling code like this.

-- Sanjoy

Hi Sanjoy,

Yes these are C tests (from 'gcc.c-torture/execute'), and as I indicated in my original message, the tests are not valid because the behaviour is undefined. However, it was while investigating these new failures in these tests that I realised that this optimisation existed.

The optimisation itself is perfectly valid, but it does mean that integer underflow will no longer be detected on systems which have hardware for this purpose.

My question is not about the validity of the optimisation - it's perfectly legitimate - but rather about whether a target can configure their TTI so as to not perform this optimisation and fall-back to using ADD instead so as to trigger integer underflow detection.

Thanks,

  MartinO

I don’t believe that this is the correct approach. You are asking for behaviour of integer overflow in C to be well-defined as trapping (which is a valid implementation of undefined behaviour). In LLVM, this would be represented as using the overflow-checking add intrinsic followed by a branch to a trap in the overflow case. The back end should then lower this to a trapping add instruction. Clang already has -ftrapv that implements almost this behaviour.

David

Yes, the hairy-edges of undefined behaviour - UB is UB.

It does mean that given:

  __attribute__((noinline)) int foo(int a, int b) { return a + b; }

  int bar1(int x) { return foo(x, INT_MIN); }
  int bar2(int x) { return x + INT_MIN; }

'bar1' and 'bar2' have different outcomes.

However, I think that the new optimisation is neat and valid and I am not suggesting that it should be changed, but it would be useful if a target could override this if they choose to do so.

  MartinO

Yes, the hairy-edges of undefined behaviour - UB is UB.

It does mean that given:

   __attribute__((noinline)) int foo(int a, int b) { return a + b; }

   int bar1(int x) { return foo(x, INT_MIN); }
   int bar2(int x) { return x + INT_MIN; }

'bar1' and 'bar2' have different outcomes.

However, I think that the new optimisation is neat and valid and I am not suggesting that it should be changed, but it would be useful if a target could override this if they choose to do so.

It might appear to be useful, but I don't think that we want to do down that road. We don't support this kind of trapping arithmetic in LLVM, the way that we define our canonical forms depend on this, and if want to support it, we need to enhance the IR with constructs that represent this in a well-defined way. Having a mode in which it "kind of works most of the time" is worse, in the long run, than just saying that it is not supported. Right now, it is not supported. I think that our experience has shown us that If we don't have a sound set of rules by which we can validate transformations, then no one really knows what they can do.

  -Hal

Thanks Hal,

I tried using the static analysers and they detect the UB nature of the expression, so the programmer still has that approach for finding this kind of bug at build time rather than run-time.

All the best,

  MartinO