From fc89f544a6998a9a4e459a2c43da42b5f17333b9 Mon Sep 17 00:00:00 2001 From: rguenth Date: Tue, 15 Apr 2014 10:18:28 +0000 Subject: [PATCH] 2014-04-15 Richard Biener * alias.c (ncr_compar): New function. (nonoverlapping_component_refs_p): Re-implement in O (n log n). git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@209413 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 5 +++ gcc/alias.c | 132 ++++++++++++++++++++++++++++++++++++++++++---------------- 2 files changed, 100 insertions(+), 37 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 1a2f425e02a..bfba5a5fdf4 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,10 @@ 2014-04-15 Richard Biener + * alias.c (ncr_compar): New function. + (nonoverlapping_component_refs_p): Re-implement in O (n log n). + +2014-04-15 Richard Biener + * alias.c (record_component_aliases): Do not walk BINFOs. 2014-04-15 Richard Biener diff --git a/gcc/alias.c b/gcc/alias.c index f8e7760e411..4b32fcb027b 100644 --- a/gcc/alias.c +++ b/gcc/alias.c @@ -2248,6 +2248,25 @@ read_dependence (const_rtx mem, const_rtx x) return false; } +/* qsort compare function to sort FIELD_DECLs after their + DECL_FIELD_CONTEXT TYPE_UID. */ + +static inline int +ncr_compar (const void *field1_, const void *field2_) +{ + const_tree field1 = *(const_tree *) const_cast (field1_); + const_tree field2 = *(const_tree *) const_cast (field2_); + unsigned int uid1 + = TYPE_UID (TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (field1))); + unsigned int uid2 + = TYPE_UID (TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (field2))); + if (uid1 < uid2) + return -1; + else if (uid1 > uid2) + return 1; + return 0; +} + /* Return true if we can determine that the fields referenced cannot overlap for any pair of objects. */ @@ -2255,7 +2274,6 @@ static bool nonoverlapping_component_refs_p (const_rtx rtlx, const_rtx rtly) { const_tree x = MEM_EXPR (rtlx), y = MEM_EXPR (rtly); - const_tree fieldx, fieldy, typex, typey, orig_y; if (!flag_strict_aliasing || !x || !y @@ -2263,49 +2281,89 @@ nonoverlapping_component_refs_p (const_rtx rtlx, const_rtx rtly) || TREE_CODE (y) != COMPONENT_REF) return false; - do + auto_vec fieldsx; + while (TREE_CODE (x) == COMPONENT_REF) { - /* The comparison has to be done at a common type, since we don't - know how the inheritance hierarchy works. */ - orig_y = y; - do - { - fieldx = TREE_OPERAND (x, 1); - typex = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldx)); - - y = orig_y; - do - { - fieldy = TREE_OPERAND (y, 1); - typey = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldy)); - - if (typex == typey) - goto found; + tree field = TREE_OPERAND (x, 1); + tree type = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (field)); + if (TREE_CODE (type) == RECORD_TYPE) + fieldsx.safe_push (field); + x = TREE_OPERAND (x, 0); + } + if (fieldsx.length () == 0) + return false; + auto_vec fieldsy; + while (TREE_CODE (y) == COMPONENT_REF) + { + tree field = TREE_OPERAND (y, 1); + tree type = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (field)); + if (TREE_CODE (type) == RECORD_TYPE) + fieldsy.safe_push (TREE_OPERAND (y, 1)); + y = TREE_OPERAND (y, 0); + } + if (fieldsy.length () == 0) + return false; - y = TREE_OPERAND (y, 0); - } - while (y && TREE_CODE (y) == COMPONENT_REF); + /* Most common case first. */ + if (fieldsx.length () == 1 + && fieldsy.length () == 1) + return ((TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldsx[0])) + == TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldsy[0]))) + && fieldsx[0] != fieldsy[0] + && !(DECL_BIT_FIELD (fieldsx[0]) && DECL_BIT_FIELD (fieldsy[0]))); - x = TREE_OPERAND (x, 0); + if (fieldsx.length () == 2) + { + if (ncr_compar (&fieldsx[0], &fieldsx[1]) == 1) + { + const_tree tem = fieldsx[0]; + fieldsx[0] = fieldsx[1]; + fieldsx[1] = tem; } - while (x && TREE_CODE (x) == COMPONENT_REF); - /* Never found a common type. */ - return false; + } + else + fieldsx.qsort (ncr_compar); - found: - /* If we're left with accessing different fields of a structure, then no - possible overlap, unless they are both bitfields. */ - if (TREE_CODE (typex) == RECORD_TYPE && fieldx != fieldy) - return !(DECL_BIT_FIELD (fieldx) && DECL_BIT_FIELD (fieldy)); + if (fieldsy.length () == 2) + { + if (ncr_compar (&fieldsy[0], &fieldsy[1]) == 1) + { + const_tree tem = fieldsy[0]; + fieldsy[0] = fieldsy[1]; + fieldsy[1] = tem; + } + } + else + fieldsy.qsort (ncr_compar); - /* The comparison on the current field failed. If we're accessing - a very nested structure, look at the next outer level. */ - x = TREE_OPERAND (x, 0); - y = TREE_OPERAND (y, 0); + unsigned i = 0, j = 0; + do + { + const_tree fieldx = fieldsx[i]; + const_tree fieldy = fieldsy[j]; + tree typex = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldx)); + tree typey = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldy)); + if (typex == typey) + { + /* We're left with accessing different fields of a structure, + no possible overlap, unless they are both bitfields. */ + if (fieldx != fieldy) + return !(DECL_BIT_FIELD (fieldx) && DECL_BIT_FIELD (fieldy)); + } + if (TYPE_UID (typex) < TYPE_UID (typey)) + { + i++; + if (i == fieldsx.length ()) + break; + } + else + { + j++; + if (j == fieldsy.length ()) + break; + } } - while (x && y - && TREE_CODE (x) == COMPONENT_REF - && TREE_CODE (y) == COMPONENT_REF); + while (1); return false; } -- 2.11.4.GIT