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);
+}
