[CodeGen] [ubsan] Respect integer overflow handling in abs builtin

[artem]

Summary

Currenly both Clang and GCC support the following set of flags that control
code gen of signed overflow:

• -fwrapv: overflow is defined as in two-complement
• -ftrapv: overflow traps
• -fsanitize=signed-integer-overflow: if undefined (no -fwrapv), then overflow behaviour is controlled by UBSan runtime, overrides -ftrapv

Howerver, clang ignores these flags for __builtin_abs(int) and its higher-width
versions, so passing minimum integer value always causes poison.

The same holds for *abs(), which are not handled in frontend at all but folded
to llvm.abs.* intrinsics during InstCombinePass. The intrinsics are not
instrumented by UBSan, so the functions need special handling as well.

This patch does a few things:

• Handle *abs() in CGBuiltin the same way as __builtin_*abs()
• -fsanitize=signed-integer-overflow now properly instruments abs() with UBSan
• -fwrapv and -ftrapv handling for abs() is made consistent with GCC

Fixes #45129 and #45794

[craig.topper]

clang/lib/CodeGen/CGBuiltin.cpp

1793

recover -> recovery?

Period at the end of the comment

[artem]

Fixed comments and failing test. Added a new compiler-rt test for ubsan

[artem]

typo fix

[artem]

Ping

[craig.topper]

This looks good to me, but I'm not sure I'm a fully qualified reviewer here.

[aaron.ballman]

Adding codegen and ubsan code owners for opinions.

clang/lib/CodeGen/CGBuiltin.cpp

1777

[efriedma]

The overall approach here seems reasonable. I mean, technically the undefined behavior is happening in the library, but detecting it early seems like a good idea.

This approach does have a significant limitation, though: CGBuiltin won't detect cases that involve taking the address of abs(). So ubsan won't end up picking up undefined behavior in such calls, and -fwrapv won't apply. Maybe that's rare enough we don't really care, though.

Needs a release note.

Do we want to update ubsan documentation to reflect this?

clang/lib/CodeGen/CGBuiltin.cpp

2679

Putting the behavior under both "builtin" and "signed-integer-overflow" feels a little weird; is there any precedent for that?

2684

Can we land the change to directly generate calls to llvm.abs() in the default case separately? This might end up impacting generated code for a variety of workloads, and I'd prefer to have a more clear bisect point.

[artem]

Thanks for the feedback! I will resolve the problems in the next revision after some clarifications.

clang/lib/CodeGen/CGBuiltin.cpp

2679

The problem is, we are instrumenting a builtin function, so on the one hand it is reasonable to be controlled by -fsanitize=builtin. On the other hand, GCC treats abs() as an arithmetic operation, so it is being instrumented by -fsanitize=signed-integer-overflow (abs(INT_MIN) causes a negation overflow).

I have decided to enable instrumentation under any of the flags, but I am not sure whether it is the right choice.

2684

I used llvm.abs() for code simplicity, since middle-end combines the instructions to it anyways. I think this part can be dropped entirely because the intrinsic is not the best possible option either (the compiler emits conditional move and fails to elide extra sign checks if the argument is known to be non-negative).

[efriedma]

clang/lib/CodeGen/CGBuiltin.cpp

2679

I'd prefer to just follow gcc here, I think, if there isn't any strong reason to pick a different approach.

2684

Sure, that works too.

[artem]

Fixed review comments

[efriedma]

LGTM

[artem]

Thanks for the review.

I do not have commit rights, could you please push it? Artem Labazov <[e-mail]>

[artem]

Ping

[thurston]

This patch might have broke the buildbots, starting with when it was first built in https://lab.llvm.org/buildbot/#/builders/85/builds/18390

/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/libcxx_build_ubsan/include/c++/v1/stdlib.h:114:25: runtime error: negation of -9223372036854775808 cannot be represented in type 'long'; cast to an unsigned type to negate this value to itself
    #0 0x5586b6dfb9aa in abs /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/libcxx_build_ubsan/include/c++/v1/stdlib.h:114:10
    #1 0x5586b6dfb9aa in (anonymous namespace)::GNUELFDumper<llvm::object::ELFType<(llvm::support::endianness)1, true>>::printRelRelaReloc((anonymous namespace)::Relocation<llvm::object::ELFType<(llvm::support::endianness)1, true>> const&, (anonymous namespace)::RelSymbol<llvm::object::ELFType<(llvm::support::endianness)1, true>> const&) /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/tools/llvm-readobj/ELFDumper.cpp:3778:21

(which is good insofar as it finds a real bug, but nonetheless is turning the buildbots red)

In the latest buildbots, the error persists (along with an unrelated failure): https://lab.llvm.org/buildbot/#/builders/85/builds/18413

The compiler code is a tad too nuanced for me to fix with confidence (e.g., my first instinct would be to widen the type to int128 but I don't know if that will break compatibility).

[craig.topper]

I just put up a patch for RISC-V failure related to this https://reviews.llvm.org/D158304 change.

[MaskRay]

clang/lib/CodeGen/CGBuiltin.cpp

1787

nit: we delete braces in this cascading case

https://llvm.org/docs/CodingStandards.html#don-t-use-braces-on-simple-single-statement-bodies-of-if-else-loop-statements

clang/test/ubsan/TestCases/Misc/abs.cpp

1

Did you mean compiler-rt/ instead of clang/?

// REQUIRES: arch=x86_64 is legacy style.

New style uses // REQUIRES: target={{x86_64.*}}

Actually, this test should be generic and we should remove REQUIRES.

[MaskRay]

In D156821#4599471, @thurston wrote:

This patch might have broke the buildbots, starting with when it was first built in https://lab.llvm.org/buildbot/#/builders/85/builds/18390

/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/libcxx_build_ubsan/include/c++/v1/stdlib.h:114:25: runtime error: negation of -9223372036854775808 cannot be represented in type 'long'; cast to an unsigned type to negate this value to itself
    #0 0x5586b6dfb9aa in abs /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/libcxx_build_ubsan/include/c++/v1/stdlib.h:114:10
    #1 0x5586b6dfb9aa in (anonymous namespace)::GNUELFDumper<llvm::object::ELFType<(llvm::support::endianness)1, true>>::printRelRelaReloc((anonymous namespace)::Relocation<llvm::object::ELFType<(llvm::support::endianness)1, true>> const&, (anonymous namespace)::RelSymbol<llvm::object::ELFType<(llvm::support::endianness)1, true>> const&) /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/tools/llvm-readobj/ELFDumper.cpp:3778:21

(which is good insofar as it finds a real bug, but nonetheless is turning the buildbots red)

In the latest buildbots, the error persists (along with an unrelated failure): https://lab.llvm.org/buildbot/#/builders/85/builds/18413

The compiler code is a tad too nuanced for me to fix with confidence (e.g., my first instinct would be to widen the type to int128 but I don't know if that will break compatibility).

Failed Tests (4):
  LLVM :: CodeGen/RISCV/rvv/fixed-vectors-int.ll
  LLVM :: CodeGen/SystemZ/ctpop-01.ll
  LLVM :: MC/ARM/basic-thumb2-instructions.s
  LLVM :: tools/llvm-readobj/ELF/relocations.test

AFAICT these failures have been fixed and the change can reland after the clang/ test is fixed.

[thurston]

In D156821#4600086, @MaskRay wrote:

Failed Tests (4):
  LLVM :: CodeGen/RISCV/rvv/fixed-vectors-int.ll
  LLVM :: CodeGen/SystemZ/ctpop-01.ll
  LLVM :: MC/ARM/basic-thumb2-instructions.s
  LLVM :: tools/llvm-readobj/ELF/relocations.test

AFAICT these failures have been fixed and the change can reland after the clang/ test is fixed.

+1. Thanks @MaskRay for fixing the MC/ARM/basic-thumb2-instructions.s and tools/llvm-readobj/ELF/relocations.test cases!

(For completeness, for anyone else following this discussion: the CodeGen/SystemZ/ctpop-01.ll failure is unrelated to this patch and was reverted in https://reviews.llvm.org/rG29b200906155da393b83232dd31d746ba2ad66a5; the RISCV case was fixed by craig.topper in https://reviews.llvm.org/D158304)

[artem]

Fixed the comments. I do not have commit rights

clang/test/ubsan/TestCases/Misc/abs.cpp

1

I think that Aaron has moved the file when committed to the main branch. Anyway, moved.

[MaskRay]

compiler-rt/test/ubsan/TestCases/Misc/abs.cpp

11 ↗

(On Diff #551656)

FYI: [[@LINE+3]] is deprecated lit syntax https://llvm.org/docs/CommandGuide/FileCheck.html#filecheck-pseudo-numeric-variables. New code should use [[#@LINE+3]]

{{[0-9]+}} can be simplified as [[#]]

[MaskRay]

clang/lib/CodeGen/CGBuiltin.cpp

1787

Thanks. I think the coding standard omits the outer braces as well.

[MaskRay]

Currenly both Clang and GCC support the following set of flags that control

code gen of signed overflow:

[...]
Howerver, clang ignores these flags for __builtin_abs(int) and its higher-width

versions, so passing minimum integer value always causes poison.

This paragraph reads as if GCC emits a trap for __builtin_abs in -ftrapv mode, but it doesn't. That said, its -fsanitize=signed-integer-overflow does handle __builtin_abs.

[craig.topper]

In D156821#4600550, @MaskRay wrote:

Currenly both Clang and GCC support the following set of flags that control

code gen of signed overflow:

[...]
Howerver, clang ignores these flags for __builtin_abs(int) and its higher-width

versions, so passing minimum integer value always causes poison.

This paragraph reads as if GCC emits a trap for __builtin_abs in -ftrapv mode, but it doesn't. That said, its -fsanitize=signed-integer-overflow does handle __builtin_abs.

On X86 at least, gcc does call __negvsi2 for __builtin_abs under -ftrapv. https://godbolt.org/z/8dhn9bsv5

[MaskRay]

In D156821#4600605, @craig.topper wrote:

In D156821#4600550, @MaskRay wrote:

Currenly both Clang and GCC support the following set of flags that control

code gen of signed overflow:

[...]
Howerver, clang ignores these flags for __builtin_abs(int) and its higher-width

versions, so passing minimum integer value always causes poison.

This paragraph reads as if GCC emits a trap for __builtin_abs in -ftrapv mode, but it doesn't. That said, its -fsanitize=signed-integer-overflow does handle __builtin_abs.

On X86 at least, gcc does call __negvsi2 for __builtin_abs under -ftrapv. https://godbolt.org/z/8dhn9bsv5

Thank you. You are right, sorry for my neglection. GCC may use either __negvsi2 or __subvsi3 for different ports.

[artem]

Rebased and fixed legacy FileCheck syntax. Gentle reminder that I do not have commit rights.

clang/lib/CodeGen/CGBuiltin.cpp

1787

Coding standard says "Use braces on the outer if"

compiler-rt/test/ubsan/TestCases/Misc/abs.cpp

11 ↗

(On Diff #551656)

Thanks! Fixed

[brooksmoses]

Just as an FYI note, this found a bug in one of our random-number generators that was taking a random 32-bit integer and applying abs() to it. Thank you!

clang/docs/ReleaseNotes.rst

- Fixed an issue where a class template specialization whose declaration is
   instantiated in one module and whose definition is instantiated in another
   module may end up with members associated with the wrong declaration of the
   class, which can result in miscompiles in some cases.
 - Fix crash on use of a variadic overloaded operator.
   (`#42535 <https://github.com/llvm/llvm-project/issues/42535>_`)
 - Fix a hang on valid C code passing a function type as an argument to
   ``typeof`` to form a function declaration.
   (`#64713 <https://github.com/llvm/llvm-project/issues/64713>_`)
+- Clang now respects ``-fwrapv`` and ``-ftrapv`` for ``__builtin_abs`` and
+  ``abs`` builtins.
+  (`#45129 <https://github.com/llvm/llvm-project/issues/45129>`_,
+  `#45794 <https://github.com/llvm/llvm-project/issues/45794>`_)
 
 Bug Fixes to Compiler Builtins
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Bug Fixes to Attribute Support
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Bug Fixes to C++ Support

 
 Static Analyzer
 ---------------
 
 .. _release-notes-sanitizers:
 
 Sanitizers
 ----------
+- ``-fsanitize=signed-integer-overflow`` now instruments ``__builtin_abs`` and
+  ``abs`` builtins.
+
 
 Python Binding Changes
 ----------------------
 
 Additional Information
 ======================
 
 A wide variety of additional information is available on the `Clang web

clang/lib/CodeGen/CGBuiltin.cpp

Value *CodeGenFunction::EmitCheckedArgForBuiltin(const Expr *E,
   EmitCheck(std::make_pair(Cond, SanitizerKind::Builtin),
             SanitizerHandler::InvalidBuiltin,
             {EmitCheckSourceLocation(E->getExprLoc()),
              llvm::ConstantInt::get(Builder.getInt8Ty(), Kind)},
             std::nullopt);
   return ArgValue;
 }
 
+static Value *EmitAbs(CodeGenFunction &CGF, Value *ArgValue, bool HasNSW) {
+  // X < 0 ? -X : X
+  // TODO: Use phi-node (for better SimplifyCFGPass)
+  Value *NegOp = CGF.Builder.CreateNeg(ArgValue, "neg", false, HasNSW);
+  Constant *Zero = llvm::Constant::getNullValue(ArgValue->getType());
+  Value *CmpResult = CGF.Builder.CreateICmpSLT(ArgValue, Zero, "abscond");
+  return CGF.Builder.CreateSelect(CmpResult, NegOp, ArgValue, "abs");
+}
+
+static Value *EmitOverflowCheckedAbs(CodeGenFunction &CGF, const CallExpr *E,
+                                     bool SanitizeOverflow) {
+  Value *ArgValue = CGF.EmitScalarExpr(E->getArg(0));
+
+  // Try to eliminate overflow check.
+  if (const auto *VCI = dyn_cast<llvm::ConstantInt>(ArgValue)) {
+    if (!VCI->isMinSignedValue()) {
+      return EmitAbs(CGF, ArgValue, true);
+    }
+  }
+
+  CodeGenFunction::SanitizerScope SanScope(&CGF);
+
+  Constant *Zero = Constant::getNullValue(ArgValue->getType());
+  Value *ResultAndOverflow = CGF.Builder.CreateBinaryIntrinsic(
+      Intrinsic::ssub_with_overflow, Zero, ArgValue);
+  Value *Result = CGF.Builder.CreateExtractValue(ResultAndOverflow, 0);
+  Value *NotOverflow = CGF.Builder.CreateNot(
+      CGF.Builder.CreateExtractValue(ResultAndOverflow, 1));
+
+  // TODO: support -ftrapv-handler.
+  if (SanitizeOverflow) {
+    CGF.EmitCheck({{NotOverflow, SanitizerKind::SignedIntegerOverflow}},
+                  SanitizerHandler::NegateOverflow,
+                  {CGF.EmitCheckSourceLocation(E->getArg(0)->getExprLoc()),
+                   CGF.EmitCheckTypeDescriptor(E->getType())},
+                  {ArgValue});
+  } else
+    CGF.EmitTrapCheck(NotOverflow, SanitizerHandler::SubOverflow);
+
+  Value *CmpResult = CGF.Builder.CreateICmpSLT(ArgValue, Zero, "abscond");
+  return CGF.Builder.CreateSelect(CmpResult, Result, ArgValue, "abs");
+}
+
 /// Get the argument type for arguments to os_log_helper.
 static CanQualType getOSLogArgType(ASTContext &C, int Size) {
   QualType UnsignedTy = C.getIntTypeForBitwidth(Size * 8, /*Signed=*/false);
   return C.getCanonicalType(UnsignedTy);
 }
 
 llvm::Function *CodeGenFunction::generateBuiltinOSLogHelperFunction(
     const analyze_os_log::OSLogBufferLayout &Layout,
EmitVAStartEnd(BuiltinID == Builtin::BI__va_start
                    BuiltinID != Builtin::BI__builtin_va_end);
     return RValue::get(nullptr);
   case Builtin::BI__builtin_va_copy: {
     Value *DstPtr = EmitVAListRef(E->getArg(0)).getPointer();
     Value *SrcPtr = EmitVAListRef(E->getArg(1)).getPointer();
     Builder.CreateCall(CGM.getIntrinsic(Intrinsic::vacopy), {DstPtr, SrcPtr});
     return RValue::get(nullptr);
   }
+  case Builtin::BIabs:
+  case Builtin::BIlabs:
+  case Builtin::BIllabs:
   case Builtin::BI__builtin_abs:
   case Builtin::BI__builtin_labs:
   case Builtin::BI__builtin_llabs: {
-    // X < 0 ? -X : X
-    // The negation has 'nsw' because abs of INT_MIN is undefined.
-    Value *ArgValue = EmitScalarExpr(E->getArg(0));
-    Value *NegOp = Builder.CreateNSWNeg(ArgValue, "neg");
-    Constant *Zero = llvm::Constant::getNullValue(ArgValue->getType());
-    Value *CmpResult = Builder.CreateICmpSLT(ArgValue, Zero, "abscond");
-    Value *Result = Builder.CreateSelect(CmpResult, NegOp, ArgValue, "abs");
+    bool SanitizeOverflow = SanOpts.has(SanitizerKind::SignedIntegerOverflow);
+
+    Value *Result;
+    switch (getLangOpts().getSignedOverflowBehavior()) {
+    case LangOptions::SOB_Defined:
+      Result = EmitAbs(*this, EmitScalarExpr(E->getArg(0)), false);
+      break;
+    case LangOptions::SOB_Undefined:
+      if (!SanitizeOverflow) {
+        Result = EmitAbs(*this, EmitScalarExpr(E->getArg(0)), true);
+        break;
+      }
+      [[fallthrough]];
+    case LangOptions::SOB_Trapping:
+      Result = EmitOverflowCheckedAbs(*this, E, SanitizeOverflow);
+      break;
+    }
     return RValue::get(Result);
   }
   case Builtin::BI__builtin_complex: {
     Value *Real = EmitScalarExpr(E->getArg(0));
     Value *Imag = EmitScalarExpr(E->getArg(1));
     return RValue::getComplex({Real, Imag});
   }
   case Builtin::BI__builtin_conj:

clang/test/CodeGen/abs-overflow.c

+// RUN: %clang_cc1 -triple x86_64-unknown-unknown -emit-llvm %s -o - -fwrapv -fsanitize=signed-integer-overflow | FileCheck %s --check-prefix=WRAPV
+// RUN: %clang_cc1 -triple x86_64-unknown-unknown -emit-llvm %s -o - -ftrapv | FileCheck %s --check-prefixes=BOTH-TRAP,TRAPV
+// RUN: %clang_cc1 -triple x86_64-unknown-unknown -emit-llvm %s -o - -fsanitize=signed-integer-overflow | FileCheck %s --check-prefixes=BOTH-TRAP,CATCH_UB
+// COM: TODO: Support -ftrapv-handler.
+
+extern int abs(int x);
+
+int absi(int x) {
+// WRAPV:   [[NEG:%.*]] = sub i32 0, [[X:%.*]]
+// WRAPV:   [[CMP:%.*]] = icmp slt i32 [[X]], 0
+// WRAPV:   [[SEL:%.*]] = select i1 [[CMP]], i32 [[NEG]], i32 [[X]]
+//
+// BOTH-TRAP:       [[NEG:%.*]] = call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 0, i32 [[X:%.*]])
+// BOTH-TRAP:       [[NEGV:%.*]] = extractvalue { i32, i1 } [[NEG]], 0
+// BOTH-TRAP:       [[OFL:%.*]] = extractvalue { i32, i1 } [[NEG]], 1
+// BOTH-TRAP:       [[NOFL:%.*]] = xor i1 [[OFL]], true
+// BOTH-TRAP:       br i1 [[NOFL]], label %[[CONT:.*]], label %[[TRAP:[a-zA-Z_.]*]]
+// BOTH-TRAP:       [[TRAP]]:
+// TRAPV-NEXT:        llvm.ubsantrap
+// CATCH_UB:          @__ubsan_handle_negate_overflow
+// BOTH-TRAP-NEXT:    unreachable
+// BOTH-TRAP:       [[CONT]]:
+// BOTH-TRAP-NEXT:    [[ABSCOND:%.*]] = icmp slt i32 [[X]], 0
+// BOTH-TRAP-NEXT:    select i1 [[ABSCOND]], i32 [[NEGV]], i32 [[X]]
+  return abs(x);
+}
+
+int babsi(int x) {
+// WRAPV:   [[NEG:%.*]] = sub i32 0, [[X:%.*]]
+// WRAPV:   [[CMP:%.*]] = icmp slt i32 [[X]], 0
+// WRAPV:   [[SEL:%.*]] = select i1 [[CMP]], i32 [[NEG]], i32 [[X]]
+//
+// BOTH-TRAP:       [[NEG:%.*]] = call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 0, i32 [[X:%.*]])
+// BOTH-TRAP:       [[NEGV:%.*]] = extractvalue { i32, i1 } [[NEG]], 0
+// BOTH-TRAP:       [[OFL:%.*]] = extractvalue { i32, i1 } [[NEG]], 1
+// BOTH-TRAP:       [[NOFL:%.*]] = xor i1 [[OFL]], true
+// BOTH-TRAP:       br i1 [[NOFL]], label %[[CONT:.*]], label %[[TRAP:[a-zA-Z_.]*]]
+// BOTH-TRAP:       [[TRAP]]:
+// TRAPV-NEXT:        llvm.ubsantrap
+// CATCH_UB:          @__ubsan_handle_negate_overflow
+// BOTH-TRAP-NEXT:    unreachable
+// BOTH-TRAP:       [[CONT]]:
+// BOTH-TRAP-NEXT:    [[ABSCOND:%.*]] = icmp slt i32 [[X]], 0
+// BOTH-TRAP-NEXT:    select i1 [[ABSCOND]], i32 [[NEGV]], i32 [[X]]
+  return __builtin_abs(x);
+}

clang/test/ubsan/TestCases/Misc/abs.cpp

+// REQUIRES: arch=x86_64
+//
+// RUN: %clangxx -fsanitize=signed-integer-overflow -w %s -O3 -o %t
+// RUN: %run %t 2>&1 | FileCheck %s --check-prefix=RECOVER
+//
+// RUN: %clangxx -fsanitize=signed-integer-overflow -fno-sanitize-recover=signed-integer-overflow -w %s -O3 -o %t.abort
+// RUN: not %run %t.abort 2>&1 | FileCheck %s --check-prefix=ABORT
+
+#include <limits.h>
+#include <stdlib.h>
+
+int main() {
+  // ABORT: abs.cpp:[[@LINE+3]]:17: runtime error: negation of -{{[0-9]+}} cannot be represented in type 'int'; cast to an unsigned type to negate this value to itself
+  // RECOVER: abs.cpp:[[@LINE+2]]:17: runtime error: negation of -{{[0-9]+}} cannot be represented in type 'int'; cast to an unsigned type to negate this value to itself
+  // RECOVER: abs.cpp:[[@LINE+2]]:7: runtime error: negation of -{{[0-9]+}} cannot be represented in type 'int'; cast to an unsigned type to negate this value to itself
+  __builtin_abs(INT_MIN);
+  abs(INT_MIN);
+
+  // RECOVER: abs.cpp:[[@LINE+2]]:18: runtime error: negation of -{{[0-9]+}} cannot be represented in type 'long'; cast to an unsigned type to negate this value to itself
+  // RECOVER: abs.cpp:[[@LINE+2]]:8: runtime error: negation of -{{[0-9]+}} cannot be represented in type 'long'; cast to an unsigned type to negate this value to itself
+  __builtin_labs(LONG_MIN);
+  labs(LONG_MIN);
+
+  // RECOVER: abs.cpp:[[@LINE+2]]:19: runtime error: negation of -{{[0-9]+}} cannot be represented in type 'long long'; cast to an unsigned type to negate this value to itself
+  // RECOVER: abs.cpp:[[@LINE+2]]:9: runtime error: negation of -{{[0-9]+}} cannot be represented in type 'long long'; cast to an unsigned type to negate this value to itself
+  __builtin_llabs(LLONG_MIN);
+  llabs(LLONG_MIN);
+
+  return 0;
+}