Bug 82494 - UBSAN in gcc/tree-data-ref.c:3427:16: runtime error: signed integer overflow: 131072 * -131072 cannot be represented in type 'int'
Summary: UBSAN in gcc/tree-data-ref.c:3427:16: runtime error: signed integer overflow:...
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: unknown
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
: 85158 (view as bug list)
Depends on:
Blocks: ubsan
  Show dependency treegraph
 
Reported: 2017-10-09 11:51 UTC by Martin Liška
Modified: 2021-09-20 11:40 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2017-10-09 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Martin Liška 2017-10-09 11:51:23 UTC
With bootstrap-ubsan I see:

$ UBSAN_OPTIONS="print_stacktrace=1" ./xgcc -B. /home/marxin/Programming/gcc2/gcc/testsuite/gcc.dg/torture/pr60183.c -c -O3
../../gcc/tree-data-ref.c:3427:16: runtime error: signed integer overflow: 131072 * -131072 cannot be represented in type 'int'
    #0 0x3a3b770 in lambda_matrix_right_hermite ../../gcc/tree-data-ref.c:3427
    #1 0x3a3c1e3 in analyze_subscript_affine_affine ../../gcc/tree-data-ref.c:3546
    #2 0x3a3e406 in analyze_siv_subscript ../../gcc/tree-data-ref.c:3794
    #3 0x3a3f8df in analyze_overlapping_iterations ../../gcc/tree-data-ref.c:4041
    #4 0x3a42e7e in subscript_dependence_tester_1 ../../gcc/tree-data-ref.c:4582
    #5 0x3a43214 in subscript_dependence_tester ../../gcc/tree-data-ref.c:4632
    #6 0x3a4361a in compute_affine_dependence(data_dependence_relation*, loop*) ../../gcc/tree-data-ref.c:4691
    #7 0x3a43b25 in compute_all_dependences(vec<data_reference*, va_heap, vl_ptr>, vec<data_dependence_relation*, va_heap, vl_ptr>*, vec<loop*, va_heap, vl_ptr>, bool) ../../gcc/tree-data-ref.c:4758
    #8 0x3a456c7 in compute_data_dependences_for_loop(loop*, bool, vec<loop*, va_heap, vl_ptr>*, vec<data_reference*, va_heap, vl_ptr>*, vec<data_dependence_relation*, va_heap, vl_ptr>*) ../../gcc/tree-data-ref.c:5156
    #9 0x1f8bc55 in tree_predictive_commoning_loop ../../gcc/tree-predcom.c:3050
    #10 0x1f8c1c2 in tree_predictive_commoning() ../../gcc/tree-predcom.c:3172
    #11 0x1f8c242 in run_tree_predictive_commoning ../../gcc/tree-predcom.c:3197
    #12 0x1f8c38d in execute ../../gcc/tree-predcom.c:3226
    #13 0x18f223a in execute_one_pass(opt_pass*) ../../gcc/passes.c:2495
    #14 0x18f2bcb in execute_pass_list_1 ../../gcc/passes.c:2584
    #15 0x18f2c80 in execute_pass_list_1 ../../gcc/passes.c:2585
    #16 0x18f2c80 in execute_pass_list_1 ../../gcc/passes.c:2585
    #17 0x18f2d1f in execute_pass_list(function*, opt_pass*) ../../gcc/passes.c:2595
    #18 0xd34522 in cgraph_node::expand() ../../gcc/cgraphunit.c:2115
    #19 0xd35b07 in expand_all_functions ../../gcc/cgraphunit.c:2251
    #20 0xd38201 in symbol_table::compile() ../../gcc/cgraphunit.c:2599
    #21 0xd38958 in symbol_table::finalize_compilation_unit() ../../gcc/cgraphunit.c:2692
    #22 0x1cdc527 in compile_file ../../gcc/toplev.c:481
    #23 0x1ce2c84 in do_compile ../../gcc/toplev.c:2037
    #24 0x1ce32b3 in toplev::main(int, char**) ../../gcc/toplev.c:2172
    #25 0x3aaf9e0 in main ../../gcc/main.c:39
    #26 0x14a79f7caf49 in __libc_start_main (/lib64/libc.so.6+0x20f49)
    #27 0x7d93b9 in _start (/home/marxin/Programming/gcc2/objdir/gcc/cc1+0x7d93b9)

../../gcc/tree-data-ref.c:3350:16: runtime error: signed integer overflow: 1073741824 + 1073741824 cannot be represented in type 'int'
    #0 0x3a3af5f in lambda_matrix_row_add ../../gcc/tree-data-ref.c:3350
    #1 0x3a3b890 in lambda_matrix_right_hermite ../../gcc/tree-data-ref.c:3432
    #2 0x3a3c1e3 in analyze_subscript_affine_affine ../../gcc/tree-data-ref.c:3546
    #3 0x3a3e406 in analyze_siv_subscript ../../gcc/tree-data-ref.c:3794
    #4 0x3a3f8df in analyze_overlapping_iterations ../../gcc/tree-data-ref.c:4041
    #5 0x3a42e7e in subscript_dependence_tester_1 ../../gcc/tree-data-ref.c:4582
    #6 0x3a43214 in subscript_dependence_tester ../../gcc/tree-data-ref.c:4632
    #7 0x3a4361a in compute_affine_dependence(data_dependence_relation*, loop*) ../../gcc/tree-data-ref.c:4691
    #8 0x3a43b25 in compute_all_dependences(vec<data_reference*, va_heap, vl_ptr>, vec<data_dependence_relation*, va_heap, vl_ptr>*, vec<loop*, va_heap, vl_ptr>, bool) ../../gcc/tree-data-ref.c:4758
    #9 0x3a456c7 in compute_data_dependences_for_loop(loop*, bool, vec<loop*, va_heap, vl_ptr>*, vec<data_reference*, va_heap, vl_ptr>*, vec<data_dependence_relation*, va_heap, vl_ptr>*) ../../gcc/tree-data-ref.c:5156
    #10 0x1f8bc55 in tree_predictive_commoning_loop ../../gcc/tree-predcom.c:3050
    #11 0x1f8c1c2 in tree_predictive_commoning() ../../gcc/tree-predcom.c:3172
    #12 0x1f8c242 in run_tree_predictive_commoning ../../gcc/tree-predcom.c:3197
    #13 0x1f8c38d in execute ../../gcc/tree-predcom.c:3226
    #14 0x18f223a in execute_one_pass(opt_pass*) ../../gcc/passes.c:2495
    #15 0x18f2bcb in execute_pass_list_1 ../../gcc/passes.c:2584
    #16 0x18f2c80 in execute_pass_list_1 ../../gcc/passes.c:2585
    #17 0x18f2c80 in execute_pass_list_1 ../../gcc/passes.c:2585
    #18 0x18f2d1f in execute_pass_list(function*, opt_pass*) ../../gcc/passes.c:2595
    #19 0xd34522 in cgraph_node::expand() ../../gcc/cgraphunit.c:2115
    #20 0xd35b07 in expand_all_functions ../../gcc/cgraphunit.c:2251
    #21 0xd38201 in symbol_table::compile() ../../gcc/cgraphunit.c:2599
    #22 0xd38958 in symbol_table::finalize_compilation_unit() ../../gcc/cgraphunit.c:2692
    #23 0x1cdc527 in compile_file ../../gcc/toplev.c:481
    #24 0x1ce2c84 in do_compile ../../gcc/toplev.c:2037
    #25 0x1ce32b3 in toplev::main(int, char**) ../../gcc/toplev.c:2172
    #26 0x3aaf9e0 in main ../../gcc/main.c:39
    #27 0x14a79f7caf49 in __libc_start_main (/lib64/libc.so.6+0x20f49)
    #28 0x7d93b9 in _start (/home/marxin/Programming/gcc2/objdir/gcc/cc1+0x7d93b9)

../../gcc/tree-data-ref.c:3429:7: runtime error: negation of -2147483648 cannot be represented in type 'int'; cast to an unsigned type to negate this value to itself
    #0 0x3a3b7ca in lambda_matrix_right_hermite ../../gcc/tree-data-ref.c:3429
    #1 0x3a3c1e3 in analyze_subscript_affine_affine ../../gcc/tree-data-ref.c:3546
    #2 0x3a3e406 in analyze_siv_subscript ../../gcc/tree-data-ref.c:3794
    #3 0x3a3f8df in analyze_overlapping_iterations ../../gcc/tree-data-ref.c:4041
    #4 0x3a42e7e in subscript_dependence_tester_1 ../../gcc/tree-data-ref.c:4582
    #5 0x3a43214 in subscript_dependence_tester ../../gcc/tree-data-ref.c:4632
    #6 0x3a4361a in compute_affine_dependence(data_dependence_relation*, loop*) ../../gcc/tree-data-ref.c:4691
    #7 0x3a43b25 in compute_all_dependences(vec<data_reference*, va_heap, vl_ptr>, vec<data_dependence_relation*, va_heap, vl_ptr>*, vec<loop*, va_heap, vl_ptr>, bool) ../../gcc/tree-data-ref.c:4758
    #8 0x3a456c7 in compute_data_dependences_for_loop(loop*, bool, vec<loop*, va_heap, vl_ptr>*, vec<data_reference*, va_heap, vl_ptr>*, vec<data_dependence_relation*, va_heap, vl_ptr>*) ../../gcc/tree-data-ref.c:5156
    #9 0x1f8bc55 in tree_predictive_commoning_loop ../../gcc/tree-predcom.c:3050
    #10 0x1f8c1c2 in tree_predictive_commoning() ../../gcc/tree-predcom.c:3172
    #11 0x1f8c242 in run_tree_predictive_commoning ../../gcc/tree-predcom.c:3197
    #12 0x1f8c38d in execute ../../gcc/tree-predcom.c:3226
    #13 0x18f223a in execute_one_pass(opt_pass*) ../../gcc/passes.c:2495
    #14 0x18f2bcb in execute_pass_list_1 ../../gcc/passes.c:2584
    #15 0x18f2c80 in execute_pass_list_1 ../../gcc/passes.c:2585
    #16 0x18f2c80 in execute_pass_list_1 ../../gcc/passes.c:2585
    #17 0x18f2d1f in execute_pass_list(function*, opt_pass*) ../../gcc/passes.c:2595
    #18 0xd34522 in cgraph_node::expand() ../../gcc/cgraphunit.c:2115
    #19 0xd35b07 in expand_all_functions ../../gcc/cgraphunit.c:2251
    #20 0xd38201 in symbol_table::compile() ../../gcc/cgraphunit.c:2599
    #21 0xd38958 in symbol_table::finalize_compilation_unit() ../../gcc/cgraphunit.c:2692
    #22 0x1cdc527 in compile_file ../../gcc/toplev.c:481
    #23 0x1ce2c84 in do_compile ../../gcc/toplev.c:2037
    #24 0x1ce32b3 in toplev::main(int, char**) ../../gcc/toplev.c:2172
    #25 0x3aaf9e0 in main ../../gcc/main.c:39
    #26 0x14a79f7caf49 in __libc_start_main (/lib64/libc.so.6+0x20f49)
    #27 0x7d93b9 in _start (/home/marxin/Programming/gcc2/objdir/gcc/cc1+0x7d93b9)

../../gcc/tree-data-ref.c:3428:7: runtime error: negation of -2147483648 cannot be represented in type 'int'; cast to an unsigned type to negate this value to itself
    #0 0x3a3b7a0 in lambda_matrix_right_hermite ../../gcc/tree-data-ref.c:3428
    #1 0x3a3c1e3 in analyze_subscript_affine_affine ../../gcc/tree-data-ref.c:3546
    #2 0x3a3e406 in analyze_siv_subscript ../../gcc/tree-data-ref.c:3794
    #3 0x3a3f8df in analyze_overlapping_iterations ../../gcc/tree-data-ref.c:4041
    #4 0x3a42e7e in subscript_dependence_tester_1 ../../gcc/tree-data-ref.c:4582
    #5 0x3a43214 in subscript_dependence_tester ../../gcc/tree-data-ref.c:4632
    #6 0x3a4361a in compute_affine_dependence(data_dependence_relation*, loop*) ../../gcc/tree-data-ref.c:4691
    #7 0x3a43b25 in compute_all_dependences(vec<data_reference*, va_heap, vl_ptr>, vec<data_dependence_relation*, va_heap, vl_ptr>*, vec<loop*, va_heap, vl_ptr>, bool) ../../gcc/tree-data-ref.c:4758
    #8 0x3a456c7 in compute_data_dependences_for_loop(loop*, bool, vec<loop*, va_heap, vl_ptr>*, vec<data_reference*, va_heap, vl_ptr>*, vec<data_dependence_relation*, va_heap, vl_ptr>*) ../../gcc/tree-data-ref.c:5156
    #9 0x1f8bc55 in tree_predictive_commoning_loop ../../gcc/tree-predcom.c:3050
    #10 0x1f8c1c2 in tree_predictive_commoning() ../../gcc/tree-predcom.c:3172
    #11 0x1f8c242 in run_tree_predictive_commoning ../../gcc/tree-predcom.c:3197
    #12 0x1f8c38d in execute ../../gcc/tree-predcom.c:3226
    #13 0x18f223a in execute_one_pass(opt_pass*) ../../gcc/passes.c:2495
    #14 0x18f2bcb in execute_pass_list_1 ../../gcc/passes.c:2584
    #15 0x18f2c80 in execute_pass_list_1 ../../gcc/passes.c:2585
    #16 0x18f2c80 in execute_pass_list_1 ../../gcc/passes.c:2585
    #17 0x18f2d1f in execute_pass_list(function*, opt_pass*) ../../gcc/passes.c:2595
    #18 0xd34522 in cgraph_node::expand() ../../gcc/cgraphunit.c:2115
    #19 0xd35b07 in expand_all_functions ../../gcc/cgraphunit.c:2251
    #20 0xd38201 in symbol_table::compile() ../../gcc/cgraphunit.c:2599
    #21 0xd38958 in symbol_table::finalize_compilation_unit() ../../gcc/cgraphunit.c:2692
    #22 0x1cdc527 in compile_file ../../gcc/toplev.c:481
    #23 0x1ce2c84 in do_compile ../../gcc/toplev.c:2037
    #24 0x1ce32b3 in toplev::main(int, char**) ../../gcc/toplev.c:2172
    #25 0x3aaf9e0 in main ../../gcc/main.c:39
    #26 0x14a79f7caf49 in __libc_start_main (/lib64/libc.so.6+0x20f49)
    #27 0x7d93b9 in _start (/home/marxin/Programming/gcc2/objdir/gcc/cc1+0x7d93b9)
Comment 1 Richard Biener 2017-10-09 12:09:02 UTC
I think there's a dup somewhere.  We've discussed that

typedef int *lambda_vector;

is simply too optimistic.  The machinery assumes this is an arbitrary precision integer ;)  A optimistic "fix" would be to make it int64_t, probably catching
most (if not all) practical cases (all overflows are possibly wrong-code!).

A real fix would involve either using gmp (ugh) or making a lot of routines
failable that are not right now plus using overflow-detecting math (and fail).
Comment 2 David Binderman 2017-10-10 15:19:17 UTC
I tried a -fsanitize=undefined build of today's gcc trunk with -O3
and the runtime errors I found are:

$ grep error: mk.out
../../trunk/gcc/tree-data-ref.c:3640:26: runtime error: signed integer overflow: 9223372036854775807 - -1 cannot be represented in type 'long int [3]'
../../trunk/gcc/tree-data-ref.c:3642:52: runtime error: signed integer overflow: -9223372036854775808 - 1 cannot be represented in type 'long int [3]'
$
Comment 3 Richard Biener 2018-04-03 07:51:48 UTC
*** Bug 85158 has been marked as a duplicate of this bug. ***
Comment 4 Richard Biener 2018-04-03 07:56:20 UTC
I commented in the dup:

This code hasn't been fixed to avoid overflows and generally expects to operate with infinite precision integers ... (you know, 32/64bits will be enough - really!).

Fixing requires overhauling all of the API and data structures in dependence analysis and finding a suitable representation for "infinite precision integers".
Note that most of the APIs do not have a well-defined failure mode so bailing
out isn't easy either.

Using GMP is very likely prohibitly expensive not only due to its lack of
optimizing the small-precision case.  OTOH we are using it from niter analysis
already.  Evaluating ISL ints (isl/val.h when configured to not use GMP) might
be worth, as well as maybe looking at including (patched?) mini-gmp (not sure
if that plays well with linking against real gmp, but eventually mpfr plays
well enough with mini-gmp and doesn't get too slow).

Note the HWIs are less likely a problem than the ints currently used for
lambda vectors/matrices.

Note that simply silencing UBSAN by using unsigned arithmetic will simply
silence it, not avoiding wrong-code issues that might be latent there.
Comment 5 Andrew Pinski 2021-09-20 11:03:54 UTC
r9-3927 changed the type from int to HOST_WIDE_INT which is always at least 64bit ...

I also wonder if we could use wi::widest_int here.
Comment 6 Richard Biener 2021-09-20 11:40:04 UTC
(In reply to Andrew Pinski from comment #5)
> r9-3927 changed the type from int to HOST_WIDE_INT which is always at least
> 64bit ...
> 
> I also wonder if we could use wi::widest_int here.

That's prohibitively expensive (storage-wise).  Note propagating a failure
upwards should in theory be possible (but it's going to "hurt" - welcome C++ exceptions?)