[RFC] GCC aliasing bug PR optimization/9745

[David Edelsohn <dje at watson dot ibm dot com>]

	With some insight by Dale Johannesen, I have tracked down the
cause of the miscompilation of libmcrypt by GCC 3.3 and the trunk, but the
problem seems to be a fundamental bug in GCC's RTL aliasing design.

	The symptom is elicited by RTL which accesses an array both
through the frame pointer and through a pseudo derived from the frame
pointer.  GCC alias analysis marks certain base registers (stack pointer,
argument pointer, frame pointer, hard frame pointer) as special using
ADDRESS.  On some architectures, such as PowerPC, the frame pointer is not
a fixed register and can be eliminated in terms of the stack pointer.

	Given mem1 offset from frame pointer and mem2 offset from a pseudo
derived from the frame pointer,

	find_base_term (mem1) = (ADDRESS:SI (frame_pointer_rtx))
	find_base_term (mem2) = (frame_pointer_rtx)

rtx_equal_p(base1, base2) returns false in base_alias_check() and
base_alias_check() believes that any base containing ADDRESS cannot alias
anything else, therefore the two MEMs must not alias each other.

	When initially recording the base register for the pseudo in mem2,
find_base_value() returns frame_pointer_rtx, not
base_reg_value[FRAME_POINTER_REGNUM] because the frame pointer is not
fixed.  The comments in find_base_value() says that fixed is required to
avoid loops.  I have tried changing both find_base_value() and
find_base_term() to handle frame_pointer_rtx specially and return the
ADDRESS base, but all cause breakage.

	Basically, GCC alias analysis seems to get confused if
frame_pointer_rtx is not fixed because it sometimes treats it as a special
ADDRESS but does not always reduce base terms to the special value.  If
the base register is the same but find_base_term() returns values that do
not equate, things break.

	The only thing that has worked to fix the problem is removing the
special ADDRESS mark from reg_base_value[FRAME_POINTER_REGNUM].  (Whether
I set it to frame_pointer_rtx or do not set it, it ends up as 0.)  This
means that GCC does not have any knowledge about the origin of the
register and the MEMs may alias.

	Appended is a patch to start some discussion.  Do other
architectures have frame_pointer_rtx != hard_frame_pointer_rtx, but
frame_pointer_rtx is fixed? 

	This failure first appeared after David Miller's patch to remove
SEQUENCE, but I do not know what the patch exposed to allow the
fundamental problem to appear.

David


Index: alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/alias.c,v
retrieving revision 1.188
diff -c -p -r1.188 alias.c
*** alias.c	26 Feb 2003 11:09:30 -0000	1.188
--- alias.c	6 Mar 2003 19:36:22 -0000
*************** nonlocal_mentioned_p_1 (loc, data)
*** 2396,2401 ****
--- 2396,2403 ----
  #endif
  		  || XEXP (base, 0) == frame_pointer_rtx))
  	    return 0;
+ 	  if (base == frame_pointer_rtx)
+ 	    return 0;
  	  /* Constants in the function's constant pool are constant.  */
  	  if (GET_CODE (base) == SYMBOL_REF && CONSTANT_POOL_ADDRESS_P (base))
  	    return 0;
*************** init_alias_once ()
*** 2695,2702 ****
      = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx);
    static_reg_base_value[ARG_POINTER_REGNUM]
      = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx);
-   static_reg_base_value[FRAME_POINTER_REGNUM]
-     = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx);
  #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
    static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
      = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
--- 2697,2702 ----