Re: [PATCH] D12793: Three new security overflow builtins with generic argument types

[John McCall via cfe-commits]

rjmccall added a comment.

X and Y aren't unreasonable for the operands, although you could also use 
"left" and "right" (or LHS/RHS), especially since it's significant for 
subtraction.  R is short for "result" and should be spelled out.  E is 
presumably short for "encompassing", but that is not immediately obvious even 
to someone reading your patch; spelling it out wouldn't hurt, or you could at 
least use a longer abbreviation.

You should also spell out the different *Ty suffixes in some way that 
differentiates them.  I don't think you actually need the *QTy variables.  The 
*ITy variables aren't really types and should not be named that way.  *LLVMTy 
is not unreasonable for the IR types.


http://reviews.llvm.org/D12793



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

Re: [PATCH] D12793: Three new security overflow builtins with generic argument types

[David Grayson via cfe-commits]

DavidEGrayson removed rL LLVM as the repository for this revision.
DavidEGrayson updated this revision to Diff 35592.
DavidEGrayson added a comment.

I have changed the patch to incorporate most of John McCall's feedback.   The 
only thing I didn't act on was the suggestion to change the names of the 
variables XITy, YITy, RITy, and EITy, because I could not think of anything 
better.


http://reviews.llvm.org/D12793

Files:
  docs/LanguageExtensions.rst
  include/clang/Basic/Builtins.def
  include/clang/Basic/DiagnosticSemaKinds.td
  lib/CodeGen/CGBuiltin.cpp
  lib/Sema/SemaChecking.cpp
  test/CodeGen/builtins-overflow-error.c
  test/CodeGen/builtins-overflow.c

Index: test/CodeGen/builtins-overflow.c
===
--- test/CodeGen/builtins-overflow.c
+++ test/CodeGen/builtins-overflow.c
@@ -11,7 +11,159 @@
 extern int IntErrorCode;
 extern long LongErrorCode;
 extern long long LongLongErrorCode;
+void overflowed(void);
 
+unsigned test_add_overflow_uint_uint_uint(unsigned x, unsigned y) {
+  // CHECK: @test_add_overflow_uint_uint_uint
+  // CHECK-NOT: ext
+  // CHECK: [[S:%.+]] = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %{{.+}}, i32 %{{.+}})
+  // CHECK-DAG: [[Q:%.+]] = extractvalue { i32, i1 } [[S]], 0
+  // CHECK-DAG: [[C:%.+]] = extractvalue { i32, i1 } [[S]], 1
+  // CHECK: store i32 [[Q]], i32* %r
+  // CHECK: br i1 [[C]]
+  unsigned r;
+  if (__builtin_add_overflow(x, y, ))
+overflowed();
+  return r;
+}
+
+int test_add_overflow_int_int_int(int x, int y) {
+  // CHECK: @test_add_overflow_int_int_int
+  // CHECK-NOT: ext
+  // CHECK: [[S:%.+]] = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %{{.+}}, i32 %{{.+}})
+  // CHECK-DAG: [[C:%.+]] = extractvalue { i32, i1 } [[S]], 1
+  // CHECK-DAG: [[Q:%.+]] = extractvalue { i32, i1 } [[S]], 0
+  // CHECK: store i32 [[Q]], i32* %r
+  // CHECK: br i1 [[C]]
+  int r;
+  if (__builtin_add_overflow(x, y, ))
+overflowed();
+  return r;
+}
+
+unsigned test_sub_overflow_uint_uint_uint(unsigned x, unsigned y) {
+  // CHECK: @test_sub_overflow_uint_uint_uint
+  // CHECK-NOT: ext
+  // CHECK: [[S:%.+]] = call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %{{.+}}, i32 %{{.+}})
+  // CHECK-DAG: [[Q:%.+]] = extractvalue { i32, i1 } [[S]], 0
+  // CHECK-DAG: [[C:%.+]] = extractvalue { i32, i1 } [[S]], 1
+  // CHECK: store i32 [[Q]], i32* %r
+  // CHECK: br i1 [[C]]
+  unsigned r;
+  if (__builtin_sub_overflow(x, y, ))
+overflowed();
+  return r;
+}
+
+int test_sub_overflow_int_int_int(int x, int y) {
+  // CHECK: @test_sub_overflow_int_int_int
+  // CHECK-NOT: ext
+  // CHECK: [[S:%.+]] = call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %{{.+}}, i32 %{{.+}})
+  // CHECK-DAG: [[C:%.+]] = extractvalue { i32, i1 } [[S]], 1
+  // CHECK-DAG: [[Q:%.+]] = extractvalue { i32, i1 } [[S]], 0
+  // CHECK: store i32 [[Q]], i32* %r
+  // CHECK: br i1 [[C]]
+  int r;
+  if (__builtin_sub_overflow(x, y, ))
+overflowed();
+  return r;
+}
+
+unsigned test_mul_overflow_uint_uint_uint(unsigned x, unsigned y) {
+  // CHECK: @test_mul_overflow_uint_uint_uint
+  // CHECK-NOT: ext
+  // CHECK: [[S:%.+]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 %{{.+}}, i32 %{{.+}})
+  // CHECK-DAG: [[Q:%.+]] = extractvalue { i32, i1 } [[S]], 0
+  // CHECK-DAG: [[C:%.+]] = extractvalue { i32, i1 } [[S]], 1
+  // CHECK: store i32 [[Q]], i32* %r
+  // CHECK: br i1 [[C]]
+  unsigned r;
+  if (__builtin_mul_overflow(x, y, ))
+overflowed();
+  return r;
+}
+
+int test_mul_overflow_int_int_int(int x, int y) {
+  // CHECK: @test_mul_overflow_int_int_int
+  // CHECK-NOT: ext
+  // CHECK: [[S:%.+]] = call { i32, i1 } @llvm.smul.with.overflow.i32(i32 %{{.+}}, i32 %{{.+}})
+  // CHECK-DAG: [[C:%.+]] = extractvalue { i32, i1 } [[S]], 1
+  // CHECK-DAG: [[Q:%.+]] = extractvalue { i32, i1 } [[S]], 0
+  // CHECK: store i32 [[Q]], i32* %r
+  // CHECK: br i1 [[C]]
+  int r;
+  if (__builtin_mul_overflow(x, y, ))
+overflowed();
+  return r;
+}
+
+int test_add_overflow_uint_int_int(unsigned x, int y) {
+  // CHECK: @test_add_overflow_uint_int_int
+  // CHECK: [[XE:%.+]] = zext i32 %{{.+}} to i33
+  // CHECK: [[YE:%.+]] = sext i32 %{{.+}} to i33
+  // CHECK: [[S:%.+]] = call { i33, i1 } @llvm.sadd.with.overflow.i33(i33 [[XE]], i33 [[YE]])
+  // CHECK-DAG: [[Q:%.+]] = extractvalue { i33, i1 } [[S]], 0
+  // CHECK-DAG: [[C1:%.+]] = extractvalue { i33, i1 } [[S]], 1
+  // CHECK: [[QT:%.+]] = trunc i33 [[Q]] to i32
+  // CHECK: [[QTE:%.+]] = sext i32 [[QT]] to i33
+  // CHECK: [[C2:%.+]] = icmp ne i33 [[Q]], [[QTE]]
+  // CHECK: [[C3:%.+]] = or i1 [[C1]], [[C2]]
+  // CHECK: store i32 [[QT]], i32* %r
+  // CHECK: br i1 [[C3]]
+  int r;
+  if (__builtin_add_overflow(x, y, ))
+overflowed();
+  return r;
+}
+
+_Bool test_add_overflow_uint_uint_bool(unsigned x, unsigned y) {
+  // CHECK: @test_add_overflow_uint_uint_bool
+  // CHECK-NOT: ext
+  // CHECK: [[S:%.+]] = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %{{.+}}, i32 

Re: [PATCH] D12793: Three new security overflow builtins with generic argument types

[David Grayson via cfe-commits]

DavidEGrayson added a comment.

Hi John.  I thought about your comment on line 1601 somewhat carefully and 
tried to imagine what it would look like.  See my inline comment.

Also, by the way, do you know if the results of the LLVM intrinsics like 
`llvm.smul.with.overflow.*` are guaranteed to be well-defined when there is an 
overflow?  This whole patch hinges on that, because the results of the builtins 
are supposed to be well-defined.  The documentation here 
 is not 
so great.



Comment at: lib/CodeGen/CGBuiltin.cpp:1601
@@ +1600,3 @@
+auto RITy = IntegerWidthAndSignedness(CGM.getContext(), RQTy);
+auto EITy = EncompassingIntegerType({XITy, YITy, RITy});
+

rjmccall wrote:
> DavidEGrayson wrote:
> > rjmccall wrote:
> > > These are not the most evocative names you could have chosen. :)
> > > 
> > > Also, this strategy is correct, but it produces horrible code when the 
> > > operands have the same signedness and the result is different, where the 
> > > result would otherwise be an ordinary operation and a compare.  You 
> > > really want to just merge the two operands and then max with the width of 
> > > the result type.
> > I don't think that would work.  It sounds like you want me to remove RITy 
> > from the call to EncompassingIntegerType.  That means the ecompassing type 
> > could be smaller than the result type, and the arithmetic intrinsic would 
> > report an overflow even though the mathematical result is representable in 
> > the result type.
> > 
> > For example, if I am multiplying ((uint8_t)100) by ((uint8_t)100) and 
> > storing the result in a (uint16_t), the result needs to be 1 and there 
> > is no overflow.  To arrive at that result, we need to convert the operands 
> > to 16-bit unsigned integers before multiplying them.  If we multiply them 
> > as 8-bit unsigned integers, the multiplication intrinsic will report an 
> > overflow and give a result of 16.  That seems like a messy situation and I 
> > don't see how a max operation would fix it.
> I think I was unclear.  I'm not saying that you should do a max as part of 
> computing the dynamic result.  I'm saying that, when deciding the 
> encompassing type, it should still be at least as wide as the result, but you 
> should ignore the result type's signedness and then patch it up with a 
> comparison at the end if necessary.  (I believe that in both cases, it's a 
> signed comparison against zero.)
> 
> That is, when multiplying two uint8_t's and storing the result in an int16_t, 
> we should just do an unsigned 16-bit multiply-with-overflow.  The computation 
> overflows if the multiply overflows (which it provably doesn't, but we can 
> let LLVM figure that out for now) or the result is signed-< 0.
OK, I understand now.  As an optimization, you would to like the operation type 
(the width/signedness that we use to perform the main math operation) to 
sometimes be the same width as the result type (the type that the third 
argument points to) but have a different sign.

I'm thinking about how that would work in all the different cases.  I have 
concluded that it would work in 5 out of 6 cases, but we would have to think 
carefully about each case and it is possible I have made some mistakes.  But 
here are the 6 cases:

1) `__builtin_add_overflow`, operation type signed, result type unsigned: It 
would work but it would be complicated.  If the signed addition intrinsic 
reports an overflow, we need to know whether the result was too big (which is 
OK) or too small (which is bad).  The most extreme underflow would be 
(-2^(N-1)) + (-2^(N-1)) = 0, so every underflow should give a non-negative 
result.  Similarly, every overflow-proper (case where the result was too big) 
would result in a negative number.  So the overflow bit returned from 
`__builtin_add_overflow` should be the overflow bit from the intrinsic XORed 
with a "less than zero" comparison.

2) `__builtin_add_overflow`, operation type unsigned, result type signed:  This 
is easier, because the only possible overflow reported by the unsigned addition 
intrinsic happens when the result is too big, which means it's definitely too 
big for the signed type.  The overflow bit returned from 
`__builtin_add_overflow` in this case would be the overflow bit from the 
intrinsic ORed with a "less than zero" comparison.

3) `__builtin_sub_overflow`, operation type signed, result type unsigned:  If 
the signed subtraction intrinsic reports an overflow, we need to know whether 
the result was too big (which is OK) or too small (which is bad).  The most 
extreme underflow would be (-2^(N-1)) - (2^(N-1)-1) = 1, so every underflow 
gives a positive value.  The most extreme overflow-proper would be (2^(N-1)-1) 
- (-2^(N-1)) = -1, so every overflow-proper gives a negative number.  Just like 
case #1, the overflow bit we return shoud be the overflow bit from the 
intrinsic 

Re: [PATCH] D12793: Three new security overflow builtins with generic argument types

[John McCall via cfe-commits]

rjmccall added a comment.

Yes, the main result is defined to be the true value mod 2^k even when overflow 
occurs.  We do use the intrinsics to implement the existing fixed-width GCC 
builtins, which are meant to be useful not just for security checking, but for 
implementing arbitrary-precision arithmetic libraries.  (LLVM doesn't seem to 
reliably do the add/adc peepholes that make that performant, though.)



Comment at: lib/CodeGen/CGBuiltin.cpp:1601
@@ +1600,3 @@
+auto RITy = IntegerWidthAndSignedness(CGM.getContext(), RQTy);
+auto EITy = EncompassingIntegerType({XITy, YITy, RITy});
+

DavidEGrayson wrote:
> rjmccall wrote:
> > DavidEGrayson wrote:
> > > rjmccall wrote:
> > > > These are not the most evocative names you could have chosen. :)
> > > > 
> > > > Also, this strategy is correct, but it produces horrible code when the 
> > > > operands have the same signedness and the result is different, where 
> > > > the result would otherwise be an ordinary operation and a compare.  You 
> > > > really want to just merge the two operands and then max with the width 
> > > > of the result type.
> > > I don't think that would work.  It sounds like you want me to remove RITy 
> > > from the call to EncompassingIntegerType.  That means the ecompassing 
> > > type could be smaller than the result type, and the arithmetic intrinsic 
> > > would report an overflow even though the mathematical result is 
> > > representable in the result type.
> > > 
> > > For example, if I am multiplying ((uint8_t)100) by ((uint8_t)100) and 
> > > storing the result in a (uint16_t), the result needs to be 1 and 
> > > there is no overflow.  To arrive at that result, we need to convert the 
> > > operands to 16-bit unsigned integers before multiplying them.  If we 
> > > multiply them as 8-bit unsigned integers, the multiplication intrinsic 
> > > will report an overflow and give a result of 16.  That seems like a messy 
> > > situation and I don't see how a max operation would fix it.
> > I think I was unclear.  I'm not saying that you should do a max as part of 
> > computing the dynamic result.  I'm saying that, when deciding the 
> > encompassing type, it should still be at least as wide as the result, but 
> > you should ignore the result type's signedness and then patch it up with a 
> > comparison at the end if necessary.  (I believe that in both cases, it's a 
> > signed comparison against zero.)
> > 
> > That is, when multiplying two uint8_t's and storing the result in an 
> > int16_t, we should just do an unsigned 16-bit multiply-with-overflow.  The 
> > computation overflows if the multiply overflows (which it provably doesn't, 
> > but we can let LLVM figure that out for now) or the result is signed-< 0.
> OK, I understand now.  As an optimization, you would to like the operation 
> type (the width/signedness that we use to perform the main math operation) to 
> sometimes be the same width as the result type (the type that the third 
> argument points to) but have a different sign.
> 
> I'm thinking about how that would work in all the different cases.  I have 
> concluded that it would work in 5 out of 6 cases, but we would have to think 
> carefully about each case and it is possible I have made some mistakes.  But 
> here are the 6 cases:
> 
> 1) `__builtin_add_overflow`, operation type signed, result type unsigned: It 
> would work but it would be complicated.  If the signed addition intrinsic 
> reports an overflow, we need to know whether the result was too big (which is 
> OK) or too small (which is bad).  The most extreme underflow would be 
> (-2^(N-1)) + (-2^(N-1)) = 0, so every underflow should give a non-negative 
> result.  Similarly, every overflow-proper (case where the result was too big) 
> would result in a negative number.  So the overflow bit returned from 
> `__builtin_add_overflow` should be the overflow bit from the intrinsic XORed 
> with a "less than zero" comparison.
> 
> 2) `__builtin_add_overflow`, operation type unsigned, result type signed:  
> This is easier, because the only possible overflow reported by the unsigned 
> addition intrinsic happens when the result is too big, which means it's 
> definitely too big for the signed type.  The overflow bit returned from 
> `__builtin_add_overflow` in this case would be the overflow bit from the 
> intrinsic ORed with a "less than zero" comparison.
> 
> 3) `__builtin_sub_overflow`, operation type signed, result type unsigned:  If 
> the signed subtraction intrinsic reports an overflow, we need to know whether 
> the result was too big (which is OK) or too small (which is bad).  The most 
> extreme underflow would be (-2^(N-1)) - (2^(N-1)-1) = 1, so every underflow 
> gives a positive value.  The most extreme overflow-proper would be 
> (2^(N-1)-1) - (-2^(N-1)) = -1, so every overflow-proper gives a negative 
> number.  Just like case #1, the overflow bit we return shoud be the overflow 
> bit from 

Re: [PATCH] D12793: Three new security overflow builtins with generic argument types

[David Grayson via cfe-commits]

DavidEGrayson added a comment.

Thanks for looking at this patch, John!  I disagreed with your comment about 
calculating the encompassing type, but I will incorporate everything else and 
make a new patch tonight or within a few days.



Comment at: docs/LanguageExtensions.rst:1720
@@ -1712,1 +1719,3 @@
+being stored there, and the function returns 1.  The behavior of these builtins
+is well-defined for all argument values.
 

rjmccall wrote:
> Hmm.  It's not necessarily truncation; you could meaningfully use these 
> intrinsics to add two small signed numbers and store the result in an 
> unsigned number.  It's the unique representative value modulo 2^n, where n is 
> the bit-width of the result.
OK, I'll change the documentation because I like your way of phrasing it, but I 
think truncation always gives you the unique representative value modulo 2^n.  
If I'm adding ((int8_t)-1) to ((int8_t)-1), the infinite-width result would be 
-2, which in infinite-width binary is 11...0.  Then we truncate it 
to 8 bits to get 1110, which is 254.  And 254 is also the unique 
representative value of -2 modulo 256.



Comment at: lib/CodeGen/CGBuiltin.cpp:289
@@ +288,3 @@
+static std::pair
+EncompassingIntegerType(std::vector> Types) {
+  assert(Types.size() > 0 && "Empty list of types.");

rjmccall wrote:
> This should just take an ArrayRef.  Also, please at least introduce a typedef 
> for your pair type, and consider just making a little struct for it.
A struct called IntegerWidthAndSignedness sounds good to me, thanks.  And I 
will learn how to use ArrayRef and use it here.


Comment at: lib/CodeGen/CGBuiltin.cpp:314
@@ +313,3 @@
+static std::pair
+IntegerWidthAndSignedness(const clang::ASTContext ,
+  const clang::QualType Type) {

rjmccall wrote:
> getIntegerWidthAndSignedness, please.
Sounds good.  That frees up the name IntegerWidthAndSignedness to be used for 
my new struct.


Comment at: lib/CodeGen/CGBuiltin.cpp:1601
@@ +1600,3 @@
+auto RITy = IntegerWidthAndSignedness(CGM.getContext(), RQTy);
+auto EITy = EncompassingIntegerType({XITy, YITy, RITy});
+

rjmccall wrote:
> These are not the most evocative names you could have chosen. :)
> 
> Also, this strategy is correct, but it produces horrible code when the 
> operands have the same signedness and the result is different, where the 
> result would otherwise be an ordinary operation and a compare.  You really 
> want to just merge the two operands and then max with the width of the result 
> type.
I don't think that would work.  It sounds like you want me to remove RITy from 
the call to EncompassingIntegerType.  That means the ecompassing type could be 
smaller than the result type, and the arithmetic intrinsic would report an 
overflow even though the mathematical result is representable in the result 
type.

For example, if I am multiplying ((uint8_t)100) by ((uint8_t)100) and storing 
the result in a (uint16_t), the result needs to be 1 and there is no 
overflow.  To arrive at that result, we need to convert the operands to 16-bit 
unsigned integers before multiplying them.  If we multiply them as 8-bit 
unsigned integers, the multiplication intrinsic will report an overflow and 
give a result of 16.  That seems like a messy situation and I don't see how a 
max operation would fix it.


Comment at: lib/CodeGen/CGBuiltin.cpp:1610
@@ +1609,3 @@
+default:
+  llvm_unreachable("Unknown security overflow builtin id.");
+case Builtin::BI__builtin_add_overflow:

rjmccall wrote:
> These aren't really security-specific; they're just arbitrary-precision.
I agree that these functions are not security-specific.  I just copied that 
message from a place a little bit lower in CGBuiltin.cpp where it was used to 
describe some other overflow builtins.  I am happy to remove the word 
"security" from both places.


Comment at: lib/CodeGen/CGBuiltin.cpp:1630
@@ +1629,3 @@
+// Extend each operand to the encompassing type.
+if (XQTy->isSignedIntegerType()) {
+  X = Builder.CreateSExt(X, ELTy);

rjmccall wrote:
> This is Builder.CreateIntegerCast(X, ELTy, XITy.second).
Thanks, I thought there had to be a function for that already but just could 
not find it.


Comment at: lib/CodeGen/CGBuiltin.cpp:1667
@@ +1666,3 @@
+// we have to extend them before storing.
+Q = Builder.CreateZExt(Q, OutPtr.getElementType());
+

rjmccall wrote:
> EmitToMemory.
Thanks again, will do.


Repository:
  rL LLVM

http://reviews.llvm.org/D12793



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

Re: [PATCH] D12793: Three new security overflow builtins with generic argument types

[John McCall via cfe-commits]

rjmccall added a comment.

Thanks for doing this; this is a great start.



Comment at: docs/LanguageExtensions.rst:1720
@@ -1712,1 +1719,3 @@
+being stored there, and the function returns 1.  The behavior of these builtins
+is well-defined for all argument values.
 

Hmm.  It's not necessarily truncation; you could meaningfully use these 
intrinsics to add two small signed numbers and store the result in an unsigned 
number.  It's the unique representative value modulo 2^n, where n is the 
bit-width of the result.


Comment at: lib/CodeGen/CGBuiltin.cpp:289
@@ +288,3 @@
+static std::pair
+EncompassingIntegerType(std::vector> Types) {
+  assert(Types.size() > 0 && "Empty list of types.");

This should just take an ArrayRef.  Also, please at least introduce a typedef 
for your pair type, and consider just making a little struct for it.


Comment at: lib/CodeGen/CGBuiltin.cpp:314
@@ +313,3 @@
+static std::pair
+IntegerWidthAndSignedness(const clang::ASTContext ,
+  const clang::QualType Type) {

getIntegerWidthAndSignedness, please.


Comment at: lib/CodeGen/CGBuiltin.cpp:1601
@@ +1600,3 @@
+auto RITy = IntegerWidthAndSignedness(CGM.getContext(), RQTy);
+auto EITy = EncompassingIntegerType({XITy, YITy, RITy});
+

These are not the most evocative names you could have chosen. :)

Also, this strategy is correct, but it produces horrible code when the operands 
have the same signedness and the result is different, where the result would 
otherwise be an ordinary operation and a compare.  You really want to just 
merge the two operands and then max with the width of the result type.


Comment at: lib/CodeGen/CGBuiltin.cpp:1610
@@ +1609,3 @@
+default:
+  llvm_unreachable("Unknown security overflow builtin id.");
+case Builtin::BI__builtin_add_overflow:

These aren't really security-specific; they're just arbitrary-precision.


Comment at: lib/CodeGen/CGBuiltin.cpp:1630
@@ +1629,3 @@
+// Extend each operand to the encompassing type.
+if (XQTy->isSignedIntegerType()) {
+  X = Builder.CreateSExt(X, ELTy);

This is Builder.CreateIntegerCast(X, ELTy, XITy.second).


Comment at: lib/CodeGen/CGBuiltin.cpp:1667
@@ +1666,3 @@
+// we have to extend them before storing.
+Q = Builder.CreateZExt(Q, OutPtr.getElementType());
+

EmitToMemory.


Repository:
  rL LLVM

http://reviews.llvm.org/D12793



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits