[Bug rtl-optimization/56965] nonoverlapping_component_refs_p is bogus

["rguenth at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56965

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ebotcazou at gcc dot gnu.org

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Besides that nonoverlapping_component_refs_p is O(3) in the size of the refs
involved.

It also seems to ignore inner VIEW_CONVERT_EXPRs which means that doing the
struct X vs. struct Y dance with a VIEW_CONVERT_EXPR exposes a similar issue
(insert suitable Ada testcase here).

In the end I'd like to get rid of nonoverlapping_component_refs_p by moving
it to the tree oracle (where there is a similar but less aggressive
aliasing_component_refs_p).

It appears to me that nonoverlapping_component_refs_p could avoid its O(3)
complexity by doing sth like

  ... search for innermost VIEW_CONVERT_EXPR and start at its base ...
  vec<pair<tree, tree>> comprefs1;
  while (handled_component_ref_p (ref))
    {
      if (TREE_CODE (ref) == COMPONENT_REF)
        comprefs.safe_push (pair (ref, TYPE_MAIN_VARIANT (TYPE_CONTEXT
(TREE_OPERAND (ref, 1)))));
      ref = TREE_OPERAND (ref, 0);
    }

same for the other ref.  Then sort the two vectors after the context type
(using TYPE_UID as key for example) and then comparing the two vectors
in lock-step.

 -> O (n * log (n))

(and we can skip over non-component-handled-components as in the code above).