This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: [RFC] Detect most integer overflows.
- From: Richard Biener <richard dot guenther at gmail dot com>
- To: Hannes Frederic Sowa <hannes at stressinduktion dot org>
- Cc: OndÅej BÃlka <neleai at seznam dot cz>, "gcc at gnu dot org" <gcc at gnu dot org>
- Date: Tue, 15 Apr 2014 15:41:53 +0200
- Subject: Re: [RFC] Detect most integer overflows.
- Authentication-results: sourceware.org; auth=none
- References: <20131026192912 dot GA25428 at domone dot podge> <20131026235014 dot GF18009 at order dot stressinduktion dot org> <CAFiYyc0+wTbE1FwwLscquWvoEtM6JQw4p5qhnhBmGtVCMkx9fQ at mail dot gmail dot com> <20140411225345 dot GQ16157 at order dot stressinduktion dot org>
On Sat, Apr 12, 2014 at 12:53 AM, Hannes Frederic Sowa
<hannes@stressinduktion.org> wrote:
> 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!
Looks reasonable for a first patch to GCC! New functions miss a
toplevel comment and the big conditionals would benefit from a comment
spelling out in a more readable way what is tested.
Note that you generally should use fold_buildN instead of buildN.
And the patch lacks additions to gcc/doc/extend.texi documenting
these builtins.
And then we come to the issue that a patch of this size requires a
copyright assignment with the FSF - do you have one covering GCC work?
Thanks,
Richard.
> 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);
> +}
>