This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH 5/5] Fix intransitive comparison in dr_group_sort_cmp
- From: Yury Gribov <y dot gribov at samsung dot com>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>
- Cc: Cong Hou <congh at google dot com>, Richard Biener <rguenther at suse dot de>
- Date: Thu, 17 Dec 2015 12:03:22 +0300
- Subject: [PATCH 5/5] Fix intransitive comparison in dr_group_sort_cmp
- Authentication-results: sourceware.org; auth=none
- References: <5672787D dot 6040105 at samsung dot com>
That's an interesting one. The original comparison function assumes that
operand_equal_p(a,b) is true iff compare_tree(a, b) == 0.
Unfortunately that's not true (functions are written by different authors).
This causes subtle violation of transitiveness.
I believe removing operand_equal_p should preserve the intended semantics
(same approach taken in another comparison function in this file -
comp_dr_with_seg_len_pair).
Cc-ing Cong Hou and Richard who are the authours.
/Yury
From 7fb1fd8b2027a3a3e2d914f8bd000fe53bffe110 Mon Sep 17 00:00:00 2001
From: Yury Gribov <tetra2005@gmail.com>
Date: Sun, 13 Dec 2015 01:30:22 +0300
Subject: [PATCH 5/5] Fix intransitive comparison in dr_group_sort_cmp.
2012-12-17 Yury Gribov <tetra2005@gmail.com>
* tree-vect-data-refs.c (dr_group_sort_cmp):
Make transitive.
Error message:
Dec 10 22:28:59 yugr-ubuntu1404 : cc1plus[23983]: qsort: comparison function is not transitive (comparison function 0xddbbf0 (/home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/cc1plus+9dbbf0), called from 0xddd233 (/home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/cc1plus+9dd233), cmdline is "/home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/testsuite/g++/../../cc1plus -quiet -nostdinc++ -I /home/yugr/build/gcc-4.9.3-patched-bootstrap/x86_64-unknown-linux-gnu/libstdc++-v3/include/x86_64-unknown-linux-gnu -I /home/yugr/build/gcc-4.9.3-patched-bootstrap/x86_64-unknown-linux-gnu/libstdc++-v3/include -I /home/yugr/src/gcc-4.9.3-patched/libstdc++-v3/libsupc++ -I /home/yugr/src/gcc-4.9.3-patched/libstdc++-v3/include/backward -I /home/yugr/src/gcc-4.9.3-patched/libstdc++-v3/testsuite/util -imultiarch x86_64-linux-gnu -iprefix /home/yugr/install/gcc-4.9.3/lib/gcc/x86_64-unknown-linux-gnu/4.9.3/ -isystem /home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/testsuite/g++/../../include -isystem /home/yugr/build/gcc-4.9.3-patched-bootstrap/gcc/testsuite/g++/../../include-fixed -D_GNU_SOURCE /home/yugr/src/gcc-4.9.3-patched/gcc/testsuite/g++.dg/vect/pr43771.cc -quiet -dumpbase pr43771.cc -msse2 -mtune=generic -march=x86-64 -auxbase-strip pr43771.s -O2 -std=c++1y -fno-diagnostics-show-caret -fdiagnostics-color=never -fmessage-length=0 -ftree-vectorize -fvect-cost-model=unlimited -fdump-tree-vect-details -o pr43771.s")
---
gcc/tree-vect-data-refs.c | 39 +++++++++++++--------------------------
1 file changed, 13 insertions(+), 26 deletions(-)
diff --git a/gcc/tree-vect-data-refs.c b/gcc/tree-vect-data-refs.c
index 7755aaa..e69875a 100644
--- a/gcc/tree-vect-data-refs.c
+++ b/gcc/tree-vect-data-refs.c
@@ -2604,42 +2604,29 @@ dr_group_sort_cmp (const void *dra_, const void *drb_)
return loopa->num < loopb->num ? -1 : 1;
/* Ordering of DRs according to base. */
- if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0))
- {
- cmp = compare_tree (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb));
- if (cmp != 0)
- return cmp;
- }
+ cmp = compare_tree (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb));
+ if (cmp != 0)
+ return cmp;
/* And according to DR_OFFSET. */
- if (!dr_equal_offsets_p (dra, drb))
- {
- cmp = compare_tree (DR_OFFSET (dra), DR_OFFSET (drb));
- if (cmp != 0)
- return cmp;
- }
+ cmp = compare_tree (DR_OFFSET (dra), DR_OFFSET (drb));
+ if (cmp != 0)
+ return cmp;
/* Put reads before writes. */
if (DR_IS_READ (dra) != DR_IS_READ (drb))
return DR_IS_READ (dra) ? -1 : 1;
/* Then sort after access size. */
- if (!operand_equal_p (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
- TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))), 0))
- {
- cmp = compare_tree (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
- TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
- if (cmp != 0)
- return cmp;
- }
+ cmp = compare_tree (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
+ TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
+ if (cmp != 0)
+ return cmp;
/* And after step. */
- if (!operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))
- {
- cmp = compare_tree (DR_STEP (dra), DR_STEP (drb));
- if (cmp != 0)
- return cmp;
- }
+ cmp = compare_tree (DR_STEP (dra), DR_STEP (drb));
+ if (cmp != 0)
+ return cmp;
/* Then sort after DR_INIT. In case of identical DRs sort after stmt UID. */
cmp = tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb));
--
1.9.1