This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [RFC] Detect most integer overflows.


Hi!

On Tue, Oct 29, 2013 at 10:41:56AM +0100, Richard Biener wrote:
> For a "quick" GCC implementation of the builtins you could expand
> them to a open-coded sequence during gimplification.  But due to
> the issues pointed out above I'm not sure it is the best interface
> to support (though now the names are taken).

I played around with gcc internals for the first time today and came
up with this. As this is my first patch to gcc I am very happy to hear
feedback. Thanks!

diff --git a/gcc/builtin-types.def b/gcc/builtin-types.def
index fba9c7d..7d01c91 100644
--- a/gcc/builtin-types.def
+++ b/gcc/builtin-types.def
@@ -134,7 +134,10 @@ DEF_PRIMITIVE_TYPE (BT_I8, builtin_type_for_size (BITS_PER_UNIT*8, 1))
 DEF_PRIMITIVE_TYPE (BT_I16, builtin_type_for_size (BITS_PER_UNIT*16, 1))
 
 DEF_POINTER_TYPE (BT_PTR_CONST_STRING, BT_CONST_STRING)
+DEF_POINTER_TYPE (BT_PTR_UINT, BT_UINT)
 DEF_POINTER_TYPE (BT_PTR_LONG, BT_LONG)
+DEF_POINTER_TYPE (BT_PTR_ULONG, BT_ULONG)
+DEF_POINTER_TYPE (BT_PTR_LONGLONG, BT_LONGLONG)
 DEF_POINTER_TYPE (BT_PTR_ULONGLONG, BT_ULONGLONG)
 DEF_POINTER_TYPE (BT_PTR_PTR, BT_PTR)
 
@@ -431,6 +434,21 @@ DEF_FUNCTION_TYPE_3 (BT_FN_VOID_VPTR_I8_INT, BT_VOID, BT_VOLATILE_PTR, BT_I8, BT
 DEF_FUNCTION_TYPE_3 (BT_FN_VOID_VPTR_I16_INT, BT_VOID, BT_VOLATILE_PTR, BT_I16, BT_INT)
 DEF_FUNCTION_TYPE_3 (BT_FN_INT_PTRPTR_SIZE_SIZE, BT_INT, BT_PTR_PTR, BT_SIZE, BT_SIZE)
 
+DEF_FUNCTION_TYPE_3 (BT_FN_BOOL_INT_INT_PTR_INT, BT_BOOL, BT_INT, BT_INT,
+		     BT_INT_PTR)
+DEF_FUNCTION_TYPE_3 (BT_FN_BOOL_LONG_LONG_PTR_LONG, BT_BOOL, BT_LONG, BT_LONG,
+		     BT_PTR_LONG)
+DEF_FUNCTION_TYPE_3 (BT_FN_BOOL_LONGLONG_LONGLONG_PTR_LONGLONG, BT_BOOL,
+		     BT_LONGLONG, BT_LONGLONG, BT_PTR_LONGLONG)
+
+DEF_FUNCTION_TYPE_3 (BT_FN_BOOL_UINT_UINT_PTR_UINT, BT_BOOL, BT_UINT, BT_UINT,
+		     BT_PTR_UINT)
+DEF_FUNCTION_TYPE_3 (BT_FN_BOOL_ULONG_ULONG_PTR_ULONG, BT_BOOL, BT_ULONG, BT_ULONG,
+		     BT_PTR_ULONG)
+DEF_FUNCTION_TYPE_3 (BT_FN_BOOL_ULONGLONG_ULONGLONG_PTR_ULONGLONG, BT_BOOL,
+		     BT_ULONGLONG, BT_ULONGLONG, BT_PTR_ULONGLONG)
+
+
 DEF_FUNCTION_TYPE_4 (BT_FN_SIZE_CONST_PTR_SIZE_SIZE_FILEPTR,
 		     BT_SIZE, BT_CONST_PTR, BT_SIZE, BT_SIZE, BT_FILEPTR)
 DEF_FUNCTION_TYPE_4 (BT_FN_INT_STRING_SIZE_CONST_STRING_VALIST_ARG,
diff --git a/gcc/builtins.def b/gcc/builtins.def
index 5a76ba3..c1f5609 100644
--- a/gcc/builtins.def
+++ b/gcc/builtins.def
@@ -853,6 +853,37 @@ DEF_GCC_BUILTIN (BUILT_IN_FILE, "FILE", BT_FN_CONST_STRING, ATTR_NOTHROW_LEAF_LI
 DEF_GCC_BUILTIN (BUILT_IN_FUNCTION, "FUNCTION", BT_FN_CONST_STRING, ATTR_NOTHROW_LEAF_LIST)
 DEF_GCC_BUILTIN (BUILT_IN_LINE, "LINE", BT_FN_INT, ATTR_NOTHROW_LEAF_LIST)
 
+/* overflow builtins. */
+DEF_GCC_BUILTIN (BUILT_IN_UADD_OVERFLOW, "uadd_overflow",
+		 BT_FN_BOOL_UINT_UINT_PTR_UINT, ATTR_NOTHROW_LEAF_LIST)
+DEF_GCC_BUILTIN (BUILT_IN_UADDL_OVERFLOW, "uaddl_overflow",
+		 BT_FN_BOOL_ULONG_ULONG_PTR_ULONG, ATTR_NOTHROW_LEAF_LIST)
+DEF_GCC_BUILTIN (BUILT_IN_UADDLL_OVERFLOW, "uaddll_overflow",
+		 BT_FN_BOOL_ULONGLONG_ULONGLONG_PTR_ULONGLONG,
+		 ATTR_NOTHROW_LEAF_LIST)
+
+DEF_GCC_BUILTIN (BUILT_IN_USUB_OVERFLOW, "usub_overflow",
+		 BT_FN_BOOL_UINT_UINT_PTR_UINT, ATTR_NOTHROW_LEAF_LIST)
+DEF_GCC_BUILTIN (BUILT_IN_USUBL_OVERFLOW, "usubl_overflow",
+		 BT_FN_BOOL_ULONG_ULONG_PTR_ULONG, ATTR_NOTHROW_LEAF_LIST)
+DEF_GCC_BUILTIN (BUILT_IN_USUBLL_OVERFLOW, "usubll_overflow",
+		 BT_FN_BOOL_ULONGLONG_ULONGLONG_PTR_ULONGLONG,
+		 ATTR_NOTHROW_LEAF_LIST)
+
+DEF_GCC_BUILTIN (BUILT_IN_SADD_OVERFLOW, "sadd_overflow",
+		 BT_FN_BOOL_INT_INT_PTR_INT, ATTR_NOTHROW_LEAF_LIST)
+DEF_GCC_BUILTIN (BUILT_IN_SADDL_OVERFLOW, "saddl_overflow",
+		 BT_FN_BOOL_LONG_LONG_PTR_LONG, ATTR_NOTHROW_LEAF_LIST)
+DEF_GCC_BUILTIN (BUILT_IN_SADDLL_OVERFLOW, "saddll_overflow",
+		 BT_FN_BOOL_LONGLONG_LONGLONG_PTR_LONGLONG, ATTR_NOTHROW_LEAF_LIST)
+
+DEF_GCC_BUILTIN (BUILT_IN_SSUB_OVERFLOW, "ssub_overflow",
+		 BT_FN_BOOL_INT_INT_PTR_INT, ATTR_NOTHROW_LEAF_LIST)
+DEF_GCC_BUILTIN (BUILT_IN_SSUBL_OVERFLOW, "ssubl_overflow",
+		 BT_FN_BOOL_LONG_LONG_PTR_LONG, ATTR_NOTHROW_LEAF_LIST)
+DEF_GCC_BUILTIN (BUILT_IN_SSUBLL_OVERFLOW, "ssubll_overflow",
+		 BT_FN_BOOL_LONGLONG_LONGLONG_PTR_LONGLONG, ATTR_NOTHROW_LEAF_LIST)
+
 /* Synchronization Primitives.  */
 #include "sync-builtins.def"
 
diff --git a/gcc/gimplify.c b/gcc/gimplify.c
index 7441784..b4494a0 100644
--- a/gcc/gimplify.c
+++ b/gcc/gimplify.c
@@ -2224,6 +2224,138 @@ maybe_fold_stmt (gimple_stmt_iterator *gsi)
   return fold_stmt (gsi);
 }
 
+/* Is this an overflow builtin? */
+
+static bool
+builtin_overflow_p(tree fndecl)
+{
+  if (!fndecl)
+    return false;
+  else if (DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
+    return false;
+  else
+    switch (DECL_FUNCTION_CODE (fndecl))
+      {
+      case BUILT_IN_UADD_OVERFLOW:
+      case BUILT_IN_UADDL_OVERFLOW:
+      case BUILT_IN_UADDLL_OVERFLOW:
+      case BUILT_IN_SADD_OVERFLOW:
+      case BUILT_IN_SADDL_OVERFLOW:
+      case BUILT_IN_SADDLL_OVERFLOW:
+      case BUILT_IN_USUB_OVERFLOW:
+      case BUILT_IN_USUBL_OVERFLOW:
+      case BUILT_IN_USUBLL_OVERFLOW:
+      case BUILT_IN_SSUB_OVERFLOW:
+      case BUILT_IN_SSUBL_OVERFLOW:
+      case BUILT_IN_SSUBLL_OVERFLOW:
+	return true;
+      default:
+	return false;
+      }
+}
+
+static tree
+gimplify_build_no_overflow_tree(enum tree_code tcode, tree res_p, tree arg1,
+				tree arg2)
+{
+  tree op, res, mod;
+
+  op = size_binop (tcode, arg1, arg2);
+  res = build2 (MEM_REF, TREE_TYPE (res_p), res_p,
+		build_int_cst (TREE_TYPE (res_p), 0));
+  mod = build2 (MODIFY_EXPR, TREE_TYPE (res), res, op);
+
+  return build2 (COMPOUND_EXPR, boolean_type_node, mod, boolean_false_node);
+}
+
+static enum gimplify_status
+gimplify_overflow_builtin(tree *expr_p)
+{
+  tree check, no_ov_tree;
+  tree arg1, arg2, res_p;
+  tree expr = *expr_p;
+  tree fndecl = get_callee_fndecl (expr);
+  location_t loc = EXPR_LOCATION(expr);
+
+  arg1 = CALL_EXPR_ARG(expr, 0);
+  arg2 = CALL_EXPR_ARG(expr, 1);
+  res_p = CALL_EXPR_ARG(expr, 2);
+
+
+  switch (DECL_FUNCTION_CODE (fndecl))
+    {
+    case BUILT_IN_SADD_OVERFLOW:
+    case BUILT_IN_SADDL_OVERFLOW:
+    case BUILT_IN_SADDLL_OVERFLOW:
+      no_ov_tree = gimplify_build_no_overflow_tree(PLUS_EXPR, res_p, arg1, arg2);
+      check = build2 (TRUTH_ORIF_EXPR, boolean_type_node,
+		      build2 (TRUTH_ANDIF_EXPR, boolean_type_node,
+			      build2 (GT_EXPR, boolean_type_node,
+				      arg2, build_int_cst (TREE_TYPE (arg2), 0)),
+			      build2 (GT_EXPR, boolean_type_node,
+				      arg1,
+				      build2 (MINUS_EXPR, TREE_TYPE (arg2),
+					      TYPE_MAX_VALUE (TREE_TYPE (arg2)),
+					      arg2))),
+		      build2 (TRUTH_ANDIF_EXPR, boolean_type_node,
+			      build2 (LT_EXPR, boolean_type_node,
+				      arg2, build_int_cst (TREE_TYPE (arg2), 0)),
+			      build2 (LT_EXPR, boolean_type_node,
+				      arg1,
+				      build2 (MINUS_EXPR, TREE_TYPE (arg2),
+					      TYPE_MIN_VALUE (TREE_TYPE (arg2)),
+					      arg2))));
+      break;
+
+    case BUILT_IN_SSUB_OVERFLOW:
+    case BUILT_IN_SSUBL_OVERFLOW:
+    case BUILT_IN_SSUBLL_OVERFLOW:
+      no_ov_tree = gimplify_build_no_overflow_tree(MINUS_EXPR, res_p, arg1, arg2);
+      check = build2 (TRUTH_ORIF_EXPR, boolean_type_node,
+		      build2 (TRUTH_ANDIF_EXPR, boolean_type_node,
+			      build2 (GT_EXPR, boolean_type_node,
+				      arg2, build_int_cst (TREE_TYPE (arg2), 0)),
+			      build2 (LT_EXPR, boolean_type_node,
+				      arg1,
+				      build2 (PLUS_EXPR, TREE_TYPE (arg2),
+					      TYPE_MIN_VALUE (TREE_TYPE (arg2)),
+					      arg2))),
+		      build2 (TRUTH_ANDIF_EXPR, boolean_type_node,
+			      build2 (LT_EXPR, boolean_type_node,
+				      arg2, build_int_cst (TREE_TYPE (arg2), 0)),
+			      build2 (GT_EXPR, boolean_type_node,
+				      arg1,
+				      build2 (PLUS_EXPR, TREE_TYPE (arg2),
+					      TYPE_MAX_VALUE (TREE_TYPE (arg2)),
+					      arg2))));
+      break;
+
+    case BUILT_IN_UADD_OVERFLOW:
+    case BUILT_IN_UADDL_OVERFLOW:
+    case BUILT_IN_UADDLL_OVERFLOW:
+      no_ov_tree = gimplify_build_no_overflow_tree(PLUS_EXPR, res_p, arg1, arg2);
+      check = build2 (LT_EXPR, boolean_type_node,
+		      build2 (MINUS_EXPR, TREE_TYPE (arg1),
+			      TYPE_MAX_VALUE (TREE_TYPE (arg1)), arg1),
+		      arg2);
+      break;
+
+    case BUILT_IN_USUB_OVERFLOW:
+    case BUILT_IN_USUBL_OVERFLOW:
+    case BUILT_IN_USUBLL_OVERFLOW:
+      no_ov_tree = gimplify_build_no_overflow_tree(MINUS_EXPR, res_p, arg1, arg2);
+      check = build2 (LT_EXPR, boolean_type_node, arg1, arg2);
+      break;
+
+    default:
+      gcc_unreachable();
+    }
+
+  *expr_p = fold_build3_loc (loc, COND_EXPR, boolean_type_node, check,
+			     boolean_true_node, no_ov_tree);
+  return GS_OK;
+}
+
 /* Gimplify the CALL_EXPR node *EXPR_P into the GIMPLE sequence PRE_P.
    WANT_VALUE is true if the result of the call is desired.  */
 
@@ -2300,6 +2432,10 @@ gimplify_call_expr (tree *expr_p, gimple_seq *pre_p, bool want_value)
       default:
         ;
       }
+
+  if (builtin_overflow_p(fndecl))
+    return gimplify_overflow_builtin(expr_p);
+
   if (fndecl && DECL_BUILT_IN (fndecl))
     {
       tree new_tree = fold_call_expr (input_location, *expr_p, !want_value);
diff --git a/gcc/testsuite/gcc.dg/builtin-overflow-1.c b/gcc/testsuite/gcc.dg/builtin-overflow-1.c
new file mode 100644
index 0000000..3bbcaa0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/builtin-overflow-1.c
@@ -0,0 +1,158 @@
+/* { dg-do run } */
+/* { dg-options "-Wall -O2 -std=gnu11" } */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <limits.h>
+
+#define SADD_IMPL(POSTFIX, TYPE, TYPE_CAPS)			\
+  static _Bool sadd ## POSTFIX (TYPE a, TYPE b, TYPE *c)	\
+  {								\
+    if (((b > 0) && (a > (TYPE_CAPS ## _MAX - b)))		\
+	|| ((b < 0) && (a < (TYPE_CAPS ## _MIN - b))))		\
+      {								\
+	return 1;						\
+      }								\
+    else							\
+      {								\
+	*c = a + b;						\
+	return 0;						\
+      }								\
+  }
+
+#define UADD_IMPL(POSTFIX, TYPE, TYPE_CAPS)		\
+  static _Bool uadd ## POSTFIX (TYPE a, TYPE b, TYPE *c) \
+  {							\
+    if (TYPE_CAPS ## _MAX - a < b)			\
+      {							\
+	return 1;					\
+      }							\
+    else						\
+      {							\
+	*c = a + b;					\
+	return 0;					\
+      }							\
+  }
+
+#define SSUB_IMPL(POSTFIX, TYPE, TYPE_CAPS)		\
+  static _Bool ssub ## POSTFIX (TYPE a, TYPE b, TYPE *c) \
+  {							\
+    if ((b > 0 && a < TYPE_CAPS ## _MIN + b)		\
+	|| (b < 0 && a > TYPE_CAPS ## _MAX + b))	\
+      {							\
+	return 1;					\
+      }							\
+    else						\
+      {							\
+	*c = a - b;					\
+	return 0;					\
+      }							\
+  }
+
+#define USUB_IMPL(POSTFIX, TYPE, TYPE_CAPS)		 \
+  static _Bool usub ## POSTFIX (TYPE a, TYPE b, TYPE *c) \
+  {							\
+  if (a < b)						\
+    {							\
+      return 1;						\
+    }							\
+  else							\
+    {							\
+      *c = a - b;					\
+      return 0;						\
+    }							\
+  }
+
+SADD_IMPL (, int, INT)
+SADD_IMPL (l, long, LONG)
+SADD_IMPL (ll, long long, LLONG)
+UADD_IMPL (, unsigned int, UINT)
+UADD_IMPL (l, unsigned long, ULONG)
+UADD_IMPL (ll, unsigned long long, ULLONG)
+SSUB_IMPL (, int, INT)
+SSUB_IMPL (l, long, LONG)
+SSUB_IMPL (ll, long long, LLONG)
+USUB_IMPL (, unsigned int, INT)
+USUB_IMPL (l, unsigned long, ULONG)
+USUB_IMPL (ll, unsigned long long, ULLONG)
+
+#define TESTOV(OP, arg1, arg2) do {			\
+  __label__ err;					\
+  typeof(arg1) _arg1 = (arg1);				\
+  typeof(arg2) _arg2 = (arg2);				\
+  (void)(&_arg1 == &_arg2);				\
+							\
+  typeof(_arg1) res, res_ref;				\
+  _Bool ov, ov_ref;					\
+							\
+  ov = __builtin_ ## OP ## _overflow(_arg1, _arg2, &res);	\
+  ov_ref = OP (_arg1, _arg2, &res_ref);			\
+  if (ov != ov_ref)					\
+    goto err;						\
+  if (ov)						\
+    break;						\
+  if (res == res_ref)					\
+    break;						\
+err:							\
+  fputs("error: " #OP " " #arg1 " " #arg2 "\n", stderr);	\
+  abort();						\
+  } while (0)
+
+#define TESTOV_COM(OP, arg1, arg2) do {			\
+    TESTOV (OP, arg1, arg2);				\
+    if (arg1 != arg2)					\
+      TESTOV (OP, arg2,arg1);				\
+  } while (0)
+
+#define CAST(x) ((typeof(type_marker))(x))
+#define ONE (CAST(1))
+#define ZERO (CAST(0))
+#define MINUS_ONE (CAST(-1))
+
+#define SIGNED_TESTCASES(OP, TYPE) do {				\
+    typeof(TYPE ## _MAX) type_marker = 0;			\
+    TESTOV_COM (OP, MINUS_ONE, MINUS_ONE);			\
+    TESTOV_COM (OP, MINUS_ONE, ONE);				\
+    TESTOV_COM (OP, MINUS_ONE, ZERO);				\
+    TESTOV_COM (OP, MINUS_ONE, TYPE ## _MAX);			\
+    TESTOV_COM (OP, MINUS_ONE, TYPE ## _MIN);			\
+    TESTOV_COM (OP, ONE, ONE);					\
+    TESTOV_COM (OP, ONE, ZERO);					\
+    TESTOV_COM (OP, ONE, TYPE ## _MAX);				\
+    TESTOV_COM (OP, ONE, TYPE ## _MIN);				\
+    TESTOV_COM (OP, ZERO, ZERO);				\
+    TESTOV_COM (OP, ZERO, TYPE ## _MAX);			\
+    TESTOV_COM (OP, ZERO, TYPE ## _MIN);			\
+    TESTOV_COM (OP, TYPE ## _MAX, TYPE ## _MAX);		\
+    TESTOV_COM (OP, TYPE ## _MAX, TYPE ## _MIN);		\
+    TESTOV_COM (OP, TYPE ## _MIN, TYPE ## _MIN);		\
+  } while (0)
+
+#define UNSIGNED_TESTCASES(OP, TYPE) do {	\
+    typeof(TYPE ## _MAX) type_marker = 0;	\
+    TESTOV_COM (OP, ONE, ONE);			\
+    TESTOV_COM (OP, ONE, ZERO);			\
+    TESTOV_COM (OP, ONE, TYPE ## _MAX);		\
+    TESTOV_COM (OP, ZERO, ZERO);			\
+    TESTOV_COM (OP, ZERO, TYPE ## _MAX);		\
+    TESTOV_COM (OP, TYPE ## _MAX, TYPE ## _MAX);	\
+  } while (0)
+
+int main(int argc, char **argv)
+{
+  SIGNED_TESTCASES(sadd, INT);
+  SIGNED_TESTCASES(saddl, LONG);
+  SIGNED_TESTCASES(saddll, LLONG);
+
+  SIGNED_TESTCASES(ssub, INT);
+  SIGNED_TESTCASES(ssubl, LONG);
+  SIGNED_TESTCASES(ssubll, LLONG);
+
+  UNSIGNED_TESTCASES(uadd, UINT);
+  UNSIGNED_TESTCASES(uaddl, ULONG);
+  UNSIGNED_TESTCASES(uaddll, ULLONG);
+
+  UNSIGNED_TESTCASES(usub, UINT);
+  UNSIGNED_TESTCASES(usubl, ULONG);
+  UNSIGNED_TESTCASES(usubll, ULLONG);
+}


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]