Expansion of __builtin_frame_address

Expansion of __builtin_frame_address

[Mark Shinwell]

Hi,

I'd like to gather some opinions and advice on the expansion of
__builtin_frame_address, as discussed on gcc-patches last year [1, 2].
This centres on the following comment in expand_builtin_return_addr
arising from revision 103294 last year:

/* For a zero count, we don't care what frame address we return, so frame
    pointer elimination is OK, and using the soft frame pointer is OK.
    For a non-zero count, we require a stable offset from the current frame
    pointer to the previous one, so we must use the hard frame pointer, and
    we must disable frame pointer elimination.  */

I believe that, when this function is used to expand
__builtin_frame_address (), the first sentence isn't true: in some cases,
a function does care about the value at count == 0.  A concrete
example is the glibc backtrace () function [3] which uses the expression
__builtin_frame_address (0) to determine the starting point for stack
traversal.  (It performs subsequent dereferences back down the chain
of frame pointers by itself.)

The wording of the comment in itself is unfortunately not the end of
the issue.  Due to the subsequent conditional testing count == 0, the
builtin can expand to an erroneous value when the following conditions
are met:

- the expansion function is invoked with count set to zero; and

- the target is such that frame_pointer_rtx and hard_frame_pointer_rtx
do not ultimately yield the same address.

An example of such an invocation occurs during compilation of the
aforementioned backtrace function, and an example of such a target is the
ARM.  Currently, calling backtrace () on such a target yields a failure.

Let us just consider how to fix the ARM case for a moment.  The obvious
thing to do is to define INITIAL_FRAME_ADDRESS_RTX.  However, the correct
semantics of such a macro definition would be to:

- set current_function_accesses_prior_frames to 1, so that FP is not
eliminated in this function; and

- return hard_frame_pointer_rtx.

I hope I'm not alone in thinking that such a side-effecting macro would
be in bad taste.

Let us come back to the more general case.  As identified above, when
expand_builtin_return_addr is used to expand __builtin_frame_address (),
we do care about the count == 0 case.  I believe that the comment should
be adjusted to reflect this whatever other changes, if any, are made.
As for the remaining problem, I suggest that we could:

(i) always return the hard frame pointer, and disable FP elimination in
the current function; or

(ii) remove this logic entirely (but preserve the means to communicate any
necessity to prevent FP elimination to reload) and insist that all
targets define INITIAL_FRAME_ADDRESS_RTX.  Any such solution should
probably adjust INITIAL_FRAME_ADDRESS_RTX so that it doesn't have to
cause a side-effect in order to communicate the information about the
frame pointer.  Or...

(iii) ...the same as option (i), but allow targets to define another macro
that will cause the default code to use the soft frame pointer rather than
the hard frame pointer, and hence allow FP elimination.  (If such a macro
were set by a particular target, am I right in thinking that it would be
safe to use the soft frame pointer even in the count >= 1 cases?)

Option (ii) is in some ways the most satisfactory, as it would provide
more certainty (particularly if another target were to be added) that
the code is doing the right thing.  However it involves a moderate amount
of work and I would assume that the current level of enthusiasm in this
regard is approximately the same as last year :-)

Option (i), which is in all but name the "solution 5" approach [1] proposed
last year, means that the "count == 0" case is elevated to the same level
of importance as the "count > 0" cases, in line with the use in
backtrace ().  The problem with this is that on platforms where the
soft and hard FPs coincide there is going to be a slight
performance degradation, as identified previously, whenever these
builtins are used.  Someone with more experience will have to enlighten
me as to whether this penalty would actually be significant: my
intuition tells me that in fact it would not be, though perhaps there are
oft-used occurrences of these builtin expansions that I don't know about.
(On how many platforms is it the case that the soft and hard FPs actually
coincide?  If there are platforms where they do _not_ coincide, then
presumably those targets can be affected in the same way as I identify
above for ARM?  I'm confused because the current code seems to assume
(in the count == 0 case) that the soft and hard FPs coincide, yet uses
the hard rather than the soft FP for count >= 1.)

Option (iii) gives the advantage of a working default and removes the
pessimization on a target-by-target basis, just when it is known to be
safe.  If I'm correct in thinking that the setting of the "soft frame
pointer" macro would enable the soft frame pointer to be used no matter
what the value of count, then this option actually permits FP elimination
than the present code.

I tend to think that option (iii) might be best, although perhaps it
is overkill and option (i) would do.  But I'm not entirely sure;
still being a gcc novice I have to admit to not being quite thoroughly
clear on this myself at this stage.  So any advice or comments would be
appreciated!

Thanks,
Mark

[1] http://gcc.gnu.org/ml/gcc-patches/2005-08/msg01068.html

[2] http://gcc.gnu.org/ml/gcc-patches/2005-08/msg01194.html

[3] sysdeps/generic/backtrace.c in a glibc distribution.

Re: Expansion of __builtin_frame_address

[Mark Mitchell]

Mark Shinwell wrote:
> Hi,
> 
> I'd like to gather some opinions and advice on the expansion of
> __builtin_frame_address, as discussed on gcc-patches last year [1, 2].
> This centres on the following comment in expand_builtin_return_addr
> arising from revision 103294 last year:

I've explicitly Cc'd Jim Wilson on this email, since he did the work in
this area that you cite.  I'm not sure whether Jim is reading GCC email
presently or not, but I want to give him every opportunity to comment.

> Let us come back to the more general case.  As identified above, when
> expand_builtin_return_addr is used to expand __builtin_frame_address (),
> we do care about the count == 0 case.  I believe that the comment should
> be adjusted to reflect this whatever other changes, if any, are made.

I think this is non-controversial.

> As for the remaining problem, I suggest that we could:
> 
> (i) always return the hard frame pointer, and disable FP elimination in
> the current function; or
> 
> (iii) ...the same as option (i), but allow targets to define another macro
> that will cause the default code to use the soft frame pointer rather than
> the hard frame pointer, and hence allow FP elimination.  (If such a macro
> were set by a particular target, am I right in thinking that it would be
> safe to use the soft frame pointer even in the count >= 1 cases?)

> I tend to think that option (iii) might be best, although perhaps it
> is overkill and option (i) would do.  But I'm not entirely sure;
> still being a gcc novice I have to admit to not being quite thoroughly
> clear on this myself at this stage.  So any advice or comments would be
> appreciated!

I agree that option (iii) is best, as it provides the ability to
optimize on platforms where that is feasible, and still provides a
working default elsewhere.  I will review and approve a suitable patch
to implement (iii), assuming that there are no objections from Jim or
others.

Thanks,

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: Expansion of __builtin_frame_address

[Mark Shinwell]

[-- Attachment #1: Type: text/plain, Size: 1743 bytes --]

Mark Mitchell wrote:
> Mark Shinwell wrote:
>> As for the remaining problem, I suggest that we could:
>>
>> (i) always return the hard frame pointer, and disable FP elimination in
>> the current function; or
>>
>> (iii) ...the same as option (i), but allow targets to define another macro
>> that will cause the default code to use the soft frame pointer rather than
>> the hard frame pointer, and hence allow FP elimination.  (If such a macro
>> were set by a particular target, am I right in thinking that it would be
>> safe to use the soft frame pointer even in the count >= 1 cases?)
> 
>> I tend to think that option (iii) might be best, although perhaps it
>> is overkill and option (i) would do.  But I'm not entirely sure;
>> still being a gcc novice I have to admit to not being quite thoroughly
>> clear on this myself at this stage.  So any advice or comments would be
>> appreciated!
> 
> I agree that option (iii) is best, as it provides the ability to
> optimize on platforms where that is feasible, and still provides a
> working default elsewhere.  I will review and approve a suitable patch
> to implement (iii), assuming that there are no objections from Jim or
> others.

This having been discussed some more, and my understanding improved,
I now believe that option (i) is in fact the correct thing to do.  The
attach patch implements this, which basically amounts to the same logic
that is currently in the compiler save for the removal of the special
case when count == 0.

OK for mainline?

Mark

--

2006-06-01  Mark Shinwell  <shinwell@codesourcery.com>

	* gcc/builtins.c (expand_builtin_return_addr): Always use
	hard_frame_pointer_rtx and prevent frame pointer elimination
	if INITIAL_FRAME_ADDRESS_RTX isn't set.

[-- Attachment #2: builtin_frame_address.patch --]
[-- Type: text/plain, Size: 1228 bytes --]

Index: gcc/builtins.c
===================================================================
--- gcc/builtins.c	(revision 114277)
+++ gcc/builtins.c	(working copy)
@@ -496,20 +496,14 @@ expand_builtin_return_addr (enum built_i
 #else
   rtx tem;
 
-  /* For a zero count, we don't care what frame address we return, so frame
-     pointer elimination is OK, and using the soft frame pointer is OK.
-     For a non-zero count, we require a stable offset from the current frame
-     pointer to the previous one, so we must use the hard frame pointer, and
-     we must disable frame pointer elimination.  */
-  if (count == 0)
-    tem = frame_pointer_rtx;
-  else 
-    {
-      tem = hard_frame_pointer_rtx;
+  /* We require a stable offset from the current frame pointer to the
+     previous one, so we must use the hard frame pointer, and we must
+     disable frame pointer elimination.  */
 
-      /* Tell reload not to eliminate the frame pointer.  */
-      current_function_accesses_prior_frames = 1;
-    }
+  tem = hard_frame_pointer_rtx;
+
+  /* Tell reload not to eliminate the frame pointer.  */
+  current_function_accesses_prior_frames = 1;
 #endif
 
   /* Some machines need special handling before we can access

Re: Expansion of __builtin_frame_address

[Jim Wilson]

Mark Shinwell wrote:
> Option (i), which is in all but name the "solution 5" approach [1] proposed
> last year, means that the "count == 0" case is elevated to the same level
> of importance as the "count > 0" cases, in line with the use in
> backtrace ().  The problem with this is that on platforms where the
> soft and hard FPs coincide there is going to be a slight
> performance degradation, as identified previously, whenever these
> builtins are used.

I don't have a problem with the proposed patch that implements this.  I 
didn't choose this option earlier because I didn't have a testcase that 
required it.  You have now supplied one (glibc backtrace), so I think it 
is now reasonable to go forward with this.

The workaround for the performance problem is for backend maintainers to 
add an appropriate definition for the INITIAL_FRAME_ADDRESS_RTX macro. 
Perhaps forcing the issue will provide some incentive to people to fix 
their backends.
-- 
Jim Wilson, GNU Tools Support, http://www.specifix.com

Re: Expansion of __builtin_frame_address

[Richard Earnshaw]

On Thu, 2006-06-01 at 16:05, Mark Shinwell wrote:
> Mark Mitchell wrote:
> > Mark Shinwell wrote:
> >> As for the remaining problem, I suggest that we could:
> >>
> >> (i) always return the hard frame pointer, and disable FP elimination in
> >> the current function; or
> >>
> >> (iii) ...the same as option (i), but allow targets to define another macro
> >> that will cause the default code to use the soft frame pointer rather than
> >> the hard frame pointer, and hence allow FP elimination.  (If such a macro
> >> were set by a particular target, am I right in thinking that it would be
> >> safe to use the soft frame pointer even in the count >= 1 cases?)
> > 
> >> I tend to think that option (iii) might be best, although perhaps it
> >> is overkill and option (i) would do.  But I'm not entirely sure;
> >> still being a gcc novice I have to admit to not being quite thoroughly
> >> clear on this myself at this stage.  So any advice or comments would be
> >> appreciated!
> > 
> > I agree that option (iii) is best, as it provides the ability to
> > optimize on platforms where that is feasible, and still provides a
> > working default elsewhere.  I will review and approve a suitable patch
> > to implement (iii), assuming that there are no objections from Jim or
> > others.
> 
> This having been discussed some more, and my understanding improved,
> I now believe that option (i) is in fact the correct thing to do.  The
> attach patch implements this, which basically amounts to the same logic
> that is currently in the compiler save for the removal of the special
> case when count == 0.
> 
> OK for mainline?
> 

I'm not keen on this.  On some machines a frame pointer is *very*
expensive, both in terms of the code required to set it up, and the
resulting loss of a register which affects code quality (in addition, on
Thumb, the frame pointer can access much less data on the stack than the
stack pointer can, so code quality is affected even more).

I can see no argument for a frame pointer being *required* for getting
the return address.  We didn't have to do this in the past, so I think
it is wrong to require that we do it now.

R.
> Mark
> 
> --
> 
> 2006-06-01  Mark Shinwell  <shinwell@codesourcery.com>
> 
> 	* gcc/builtins.c (expand_builtin_return_addr): Always use
> 	hard_frame_pointer_rtx and prevent frame pointer elimination
> 	if INITIAL_FRAME_ADDRESS_RTX isn't set.

Re: Expansion of __builtin_frame_address

[Mark Shinwell]

Richard Earnshaw wrote:
> I'm not keen on this.  On some machines a frame pointer is *very*
> expensive, both in terms of the code required to set it up, and the
> resulting loss of a register which affects code quality (in addition, on
> Thumb, the frame pointer can access much less data on the stack than the
> stack pointer can, so code quality is affected even more).

Do you have anything in mind that would be a better default?  Is there
something that could be used instead of hard_frame_pointer_rtx that
will later expand to the correct frame address, but not necessarily force
use of a frame pointer, for example?  (As far as I can tell,
frame_pointer_rtx will not do at least in the ARM case, because it doesn't
yield the same value.)

If the hard frame pointer is forced by default, then targets which are
particularly badly affected can simply define INITIAL_FRAME_ADDRESS_RTX.
Since such targets would presumably not have to force reload to keep
the frame pointer, then definitions of such macros would not need to
be side-effecting (in the way described earlier in this thread) and thus
be satisfactory.

> I can see no argument for a frame pointer being *required* for getting
> the return address.  We didn't have to do this in the past, so I think
> it is wrong to require that we do it now.

Currently, the code does require a frame pointer in all except the
count == 0 case, and as far as that particular case goes I get the
impression that it would have been treated in the same way had this
glibc backtrace function been noticed last year.  This may be a mistaken
impression though.

Mark

Re: Expansion of __builtin_frame_address

[David Edelsohn]

>>>>> Mark Shinwell writes:

Mark> If the hard frame pointer is forced by default, then targets which are
Mark> particularly badly affected can simply define INITIAL_FRAME_ADDRESS_RTX.
Mark> Since such targets would presumably not have to force reload to keep
Mark> the frame pointer, then definitions of such macros would not need to
Mark> be side-effecting (in the way described earlier in this thread) and thus
Mark> be satisfactory.

	PowerPC also does not need hard_frame_pointer_rtx for all cases.
It seems like a bad idea to force every port to define
INITIAL_FRAME_ADDRESS_RTX to avoid a penalty.  Why can't whatever port
needs this change define INITIAL_FRAME_ADDRESS_RTX to
hard_frame_pointer_rtx?   One could add "count" to the macro so that the
port can optimize further and avoid hard_frame_pointer_rtx, if possible.

David

Re: Expansion of __builtin_frame_address

[Mark Shinwell]

[-- Attachment #1: Type: text/plain, Size: 1642 bytes --]

David Edelsohn wrote:
>>>>>> Mark Shinwell writes:
> 
> Mark> If the hard frame pointer is forced by default, then targets which are
> Mark> particularly badly affected can simply define INITIAL_FRAME_ADDRESS_RTX.
> Mark> Since such targets would presumably not have to force reload to keep
> Mark> the frame pointer, then definitions of such macros would not need to
> Mark> be side-effecting (in the way described earlier in this thread) and thus
> Mark> be satisfactory.
> 
> 	PowerPC also does not need hard_frame_pointer_rtx for all cases.
> It seems like a bad idea to force every port to define
> INITIAL_FRAME_ADDRESS_RTX to avoid a penalty.  Why can't whatever port
> needs this change define INITIAL_FRAME_ADDRESS_RTX to
> hard_frame_pointer_rtx?   One could add "count" to the macro so that the
> port can optimize further and avoid hard_frame_pointer_rtx, if possible.

OK, here is what I think is a better suggestion.  First note that
expand_builtin_return_addr is used for both __builtin_frame_address and
__builtin_return_address.  The behaviour for the return address
case seems to be for target-specific code to override the result of this
function in the case when count == 0; thus, it does indeed not matter what
we return from expand_builtin_return_addr in that case.  (I hadn't
realised this before.)  The new patch, below, thus has the same behaviour
for __builtin_return_address.

However when dealing with __builtin_frame_address, we must return the
correct value from this function no matter what the value of count.  This
patch therefore forces use of a hard FP in such situations.

Is that more satisfactory?

Mark

[-- Attachment #2: builtins.c.patch --]
[-- Type: text/plain, Size: 1182 bytes --]

Index: builtins.c
===================================================================
--- builtins.c	(revision 114325)
+++ builtins.c	(working copy)
@@ -496,12 +496,16 @@ expand_builtin_return_addr (enum built_i
 #else
   rtx tem;
 
-  /* For a zero count, we don't care what frame address we return, so frame
-     pointer elimination is OK, and using the soft frame pointer is OK.
-     For a non-zero count, we require a stable offset from the current frame
-     pointer to the previous one, so we must use the hard frame pointer, and
+  /* For a zero count with __builtin_return_address, we don't care what
+     frame address we return, because target-specific definitions will
+     override us.  Therefore frame pointer elimination is OK, and using
+     the soft frame pointer is OK.
+
+     For a non-zero count, or a zero count with __builtin_frame_address,
+     we require a stable offset from the current frame pointer to the
+     previous one, so we must use the hard frame pointer, and
      we must disable frame pointer elimination.  */
-  if (count == 0)
+  if (count == 0 && fndecl_code == BUILT_IN_RETURN_ADDRESS)
     tem = frame_pointer_rtx;
   else 
     {

Re: Expansion of __builtin_frame_address

[Richard Earnshaw]

On Fri, 2006-06-02 at 14:57, Mark Shinwell wrote:
> Richard Earnshaw wrote:
> > I'm not keen on this.  On some machines a frame pointer is *very*
> > expensive, both in terms of the code required to set it up, and the
> > resulting loss of a register which affects code quality (in addition, on
> > Thumb, the frame pointer can access much less data on the stack than the
> > stack pointer can, so code quality is affected even more).
> 
> Do you have anything in mind that would be a better default?  Is there
> something that could be used instead of hard_frame_pointer_rtx that
> will later expand to the correct frame address, but not necessarily force
> use of a frame pointer, for example?  (As far as I can tell,
> frame_pointer_rtx will not do at least in the ARM case, because it doesn't
> yield the same value.)
> 

Well in the past the ARM prologue code would copy the return address
into a pseudo if the body of the function invoked
__builtin_return_address, then the body of the code just used the
psuedo.  Somebody found a reason to change this, but I can't remember
why.

> If the hard frame pointer is forced by default, then targets which are
> particularly badly affected can simply define INITIAL_FRAME_ADDRESS_RTX.
> Since such targets would presumably not have to force reload to keep
> the frame pointer, then definitions of such macros would not need to
> be side-effecting (in the way described earlier in this thread) and thus
> be satisfactory.
> 
> > I can see no argument for a frame pointer being *required* for getting
> > the return address.  We didn't have to do this in the past, so I think
> > it is wrong to require that we do it now.
> 
> Currently, the code does require a frame pointer in all except the
> count == 0 case, and as far as that particular case goes I get the
> impression that it would have been treated in the same way had this
> glibc backtrace function been noticed last year.  This may be a mistaken
> impression though.

__builtin_frame_address(n) is not required to work for any value other
than n=0.  It's not clear what it means anyway on a function that
eliminates the frame pointer.

On ARM you *cannot* walk the stack frames without additional
information.  Frames are private to each function and there is no
defined format for the layout.  In particular the layout (and the frame
pointer register) is different for ARM and Thumb code, but the two can
be freely intermixed.

The only chance you have for producing a backtrace() is to have
unwinding information similar to that provided for exception unwinding. 
This would describe to the unwinder how that frames code is laid out so
that it can unpick it.

R.

Re: Expansion of __builtin_frame_address

[Richard Earnshaw]

On Fri, 2006-06-02 at 15:30, Mark Shinwell wrote:

> However when dealing with __builtin_frame_address, we must return the
> correct value from this function no matter what the value of count.  This
> patch therefore forces use of a hard FP in such situations.

Eh?  The manual explicitly says that __builtin_frame_address is only
required to work if count=0.  You simply cannot up walk arbitrary
numbers of frames on some CPUs since code isn't compiled to support it.

R.

Re: Expansion of __builtin_frame_address

[Daniel Jacobowitz]

On Fri, Jun 02, 2006 at 04:20:21PM +0100, Richard Earnshaw wrote:
> On Fri, 2006-06-02 at 15:30, Mark Shinwell wrote:
> 
> > However when dealing with __builtin_frame_address, we must return the
> > correct value from this function no matter what the value of count.  This
> > patch therefore forces use of a hard FP in such situations.
> 
> Eh?  The manual explicitly says that __builtin_frame_address is only
> required to work if count=0.  You simply cannot up walk arbitrary
> numbers of frames on some CPUs since code isn't compiled to support it.

Right - it's the result of __builtin_frame_address (0) we're looking at
here.

Mark's latest change seems logical to me: the user has asked for the
frame address, so hadn't we better arrange that there's a frame?

-- 
Daniel Jacobowitz
CodeSourcery

Re: Expansion of __builtin_frame_address

[Paul Brook]

> __builtin_frame_address(n) is not required to work for any value other
> than n=0.  It's not clear what it means anyway on a function that
> eliminates the frame pointer.
>
> On ARM you *cannot* walk the stack frames without additional
> information.  Frames are private to each function and there is no
> defined format for the layout.  In particular the layout (and the frame
> pointer register) is different for ARM and Thumb code, but the two can
> be freely intermixed.
>
> The only chance you have for producing a backtrace() is to have
> unwinding information similar to that provided for exception unwinding.
> This would describe to the unwinder how that frames code is laid out so
> that it can unpick it.

I agree that in general you need ancillary information way to get a backtrace 
on Arm. However if you assume only Arm code code and -fno-omit-frame-pointer 
then you can walk the frames. Given this assumption I think it make sense to 
have _b_f_a(0) force the use of a frame pointer.

If you're implementing "proper" unwinding then I'd say you want to use an 
assembly function stub to determine the initial frame, rather than relying on 
a rather ill-defined gcc builtin function. In other words 
__builtin_frame_address is effectively useless, so we may as well make it 
consistent with historical use than try to optimize it.

Th background to this problem is we have a client who was upset when 
backtrace() "broke" with gcc4. For this particular client 
-marm -fno-omit-frame-pointer -mapcs-frame is an acceptable price to play for 
making backtrace() work.

Paul

Re: Expansion of __builtin_frame_address

[Richard Earnshaw]

On Fri, 2006-06-02 at 16:28, Paul Brook wrote:
> I agree that in general you need ancillary information way to get a backtrace 
> on Arm. However if you assume only Arm code code and -fno-omit-frame-pointer 
> then you can walk the frames. Given this assumption I think it make sense to 
> have _b_f_a(0) force the use of a frame pointer.
> 

No, in the general case you can't.  Because ARM and Thumb frames are
laid out differently.  In ARM code the frame pointer is in r11 (when not
eliminated); in thumb code it is in r7 (because r11 can't be used in
memory insns).

R.

Re: Expansion of __builtin_frame_address

[Daniel Jacobowitz]

On Fri, Jun 02, 2006 at 04:32:07PM +0100, Richard Earnshaw wrote:
> On Fri, 2006-06-02 at 16:28, Paul Brook wrote:
> > I agree that in general you need ancillary information way to get a backtrace 
> > on Arm. However if you assume only Arm code code and -fno-omit-frame-pointer 
> > then you can walk the frames. Given this assumption I think it make sense to 
> > have _b_f_a(0) force the use of a frame pointer.
> > 
> 
> No, in the general case you can't.  Because ARM and Thumb frames are
> laid out differently.  In ARM code the frame pointer is in r11 (when not
> eliminated); in thumb code it is in r7 (because r11 can't be used in
> memory insns).

I'm reading these two paragraphs and the two of you seem to be in
violent agreement.  Paul assumed ARM code only.

-- 
Daniel Jacobowitz
CodeSourcery

Re: Expansion of __builtin_frame_address

[Mark Mitchell]

Richard Earnshaw wrote:

> The only chance you have for producing a backtrace() is to have
> unwinding information similar to that provided for exception unwinding. 
> This would describe to the unwinder how that frames code is laid out so
> that it can unpick it.

I'd suggest we leave backtrace() aside, and just talk about
__builtin_frame_address(0), which does have well-defined semantics.
_b_f_a(0) is currently broken on ARM, and we all agree we should fix it.

I mildly disagree with David's comment that:

> It seems like a bad idea to force every port to define
> INITIAL_FRAME_ADDRESS_RTX to avoid a penalty.

in that I think the default should be working code, and Mark's change
accomplishes that.

Of course, if _b_f_a(0) can be implemented more efficiently on some
target, there should be a hook to do that.  And, I think it's reasonable
to ask Mark to go through and add that optimization to ports that
already work that way, so that his patch doesn't regress any target.
(I'm not actually sure how _b_f_a(0) works on other targets, but not on
ARM.)

But, scrapping about the default probably isn't very productive.  The
important thing is to work out how _b_f_a(0) can be made to work on ARM.

Richard, I can't tell from your comments how you think _b_f_a(0) should
be implemented on ARM.  We could use Mark's logic (forcing a hard frame
pointer), but stuff it into INITIAL_FRAME_ADDRESS_RTX.  We could also
try to reimplement the thing you mentioned about using a pseudo, though
I guess we'd need to work out why that was thought a bad idea before.
What option do you suggest?

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: Expansion of __builtin_frame_address

[Richard Earnshaw]

On Fri, 2006-06-02 at 16:35, Daniel Jacobowitz wrote:
> On Fri, Jun 02, 2006 at 04:32:07PM +0100, Richard Earnshaw wrote:
> > On Fri, 2006-06-02 at 16:28, Paul Brook wrote:
> > > I agree that in general you need ancillary information way to get a backtrace 
> > > on Arm. However if you assume only Arm code code and -fno-omit-frame-pointer 
> > > then you can walk the frames. Given this assumption I think it make sense to 
> > > have _b_f_a(0) force the use of a frame pointer.
> > > 
> > 
> > No, in the general case you can't.  Because ARM and Thumb frames are
> > laid out differently.  In ARM code the frame pointer is in r11 (when not
> > eliminated); in thumb code it is in r7 (because r11 can't be used in
> > memory insns).
> 
> I'm reading these two paragraphs and the two of you seem to be in
> violent agreement.  Paul assumed ARM code only.

Well, that's a pretty limiting assumption given that ARM and thumb code
can be freely intermixed.  Indeed, I've often wondered if -Os should
default to Thumb code on CPUs that can support it (and thumb code can
corrupt the ARM frame register since it doesn't consider it to be
special in any way -- it's just a call-saved register).  I've also
pondered making the compiler ignore -f[no-]omit-frame-pointer and to
only use one in cases where the stack is dynamically adjustable.

R.

Re: Expansion of __builtin_frame_address

[Paul Brook]

On Friday 02 June 2006 16:44, Richard Earnshaw wrote:
> On Fri, 2006-06-02 at 16:35, Daniel Jacobowitz wrote:
> > On Fri, Jun 02, 2006 at 04:32:07PM +0100, Richard Earnshaw wrote:
> > > On Fri, 2006-06-02 at 16:28, Paul Brook wrote:
> > > > I agree that in general you need ancillary information way to get a
> > > > backtrace on Arm. However if you assume only Arm code code and
> > > > -fno-omit-frame-pointer then you can walk the frames. Given this
> > > > assumption I think it make sense to have _b_f_a(0) force the use of a
> > > > frame pointer.
> > >
> > > No, in the general case you can't.  Because ARM and Thumb frames are
> > > laid out differently.  In ARM code the frame pointer is in r11 (when
> > > not eliminated); in thumb code it is in r7 (because r11 can't be used
> > > in memory insns).
> >
> > I'm reading these two paragraphs and the two of you seem to be in
> > violent agreement.  Paul assumed ARM code only.
>
> Well, that's a pretty limiting assumption given that ARM and thumb code
> can be freely intermixed.  Indeed, I've often wondered if -Os should
> default to Thumb code on CPUs that can support it (and thumb code can
> corrupt the ARM frame register since it doesn't consider it to be
> special in any way -- it's just a call-saved register).  I've also
> pondered making the compiler ignore -f[no-]omit-frame-pointer and to
> only use one in cases where the stack is dynamically adjustable.

Ok, let me put it a different way.

How is __builtin_frame_address(0) useful if you don't make these assumptions, 
and what would it be used for?

For the record I agree that __builtin_return_address(0) has use and should not 
force a frame pointer.

Paul

Re: Expansion of __builtin_frame_address

[Richard Earnshaw]

On Fri, 2006-06-02 at 16:46, Mark Mitchell wrote:
> Richard, I can't tell from your comments how you think _b_f_a(0) should
> be implemented on ARM.  We could use Mark's logic (forcing a hard frame
> pointer), but stuff it into INITIAL_FRAME_ADDRESS_RTX.  We could also
> try to reimplement the thing you mentioned about using a pseudo, though
> I guess we'd need to work out why that was thought a bad idea before.
> What option do you suggest?

I think I need to understand first what _b_f_a(0) would be used for. 
Until I understand that I can't really say how best it should be
implemented.  One _possible_ implementation that would be reasonable
would be the dwarf CFA value for the function: but that's very different
from both the current ARM r11 value or the Thumb r7 value in functions
that use a frame register.  However, it is well defined in both ARM and
Thumb code.

Note that in ARM code r11 points near to the top of the frame, but in
Thumb code r7 points to the bottom of the frame (in gcc-4.2 or later,
since you can't use negative offsets in memory addresses).

R.

Re: Expansion of __builtin_frame_address

[Richard Sandiford]

Mark Mitchell <mark@codesourcery.com> writes:
> I'd suggest we leave backtrace() aside, and just talk about
> __builtin_frame_address(0), which does have well-defined semantics.
> _b_f_a(0) is currently broken on ARM, and we all agree we should fix it.

I don't want to fan the flames here, but I'm not sure either statement
is true.  Does __builtin_frame_address(0) really have well-defined
semantics on a target for which the ABI does not specify a frame layout?
I think that's Richard's point.

If I've understood the ARM case, then ARM is in the same boat as MIPS:
everything about the frame is an internal implementation detail.  I don't
think you can deference anything relative to __builtin_frame_address(0) on
MIPS and assume that it contains a particular value.

(Ironically, on MIPS, the soft frame pointer is if anything more stable
than the hard frame pointer.  The way things are set up in gcc, the soft
frame pointer always points to the bottom of the initial frame, whereas
in MIPS16 code, the hard frame pointer is offset from the soft frame
pointer by the size of the outgoing arguments.)

I'm probably going over old ground here, but:

    The frame is the area on the stack which holds local variables and saved
    registers.  The frame address is normally the address of the first word
    pushed on to the stack by the function.  However, the exact definition
    depends upon the processor and the calling convention.  If the processor
    has a dedicated frame pointer register, and the function has a frame,
    then @code{__builtin_frame_address} will return the value of the frame
    pointer register.

doesn't seem very well-defined from a predictability point of view,
since a user cannot in general know if "the function has a frame".
In some sense though, it argues that MarkS's patch isn't quite doing
what the documentation implies, since his patch effectively forces
_every_ caller of __builtin_frame_address to have a frame.

You can then argue about whether $30 on MIPS counts as "the _processor_
having a dedicated frame pointer register".  I'd say no, but...

(FWIW, MIPS is also like ARM in that MIPS gcc uses a different hard
frame pointer -- $17 -- for MIPS16 code.)

Richard

Re: Expansion of __builtin_frame_address

[Mark Mitchell]

Richard Sandiford wrote:
> Mark Mitchell <mark@codesourcery.com> writes:
>> I'd suggest we leave backtrace() aside, and just talk about
>> __builtin_frame_address(0), which does have well-defined semantics.
>> _b_f_a(0) is currently broken on ARM, and we all agree we should fix it.
> 
> I don't want to fan the flames here, but I'm not sure either statement
> is true.  Does __builtin_frame_address(0) really have well-defined
> semantics on a target for which the ABI does not specify a frame layout?
> I think that's Richard's point.

Thanks for explaining; after the latest messages from you and Richard
E., I understand the ARM doesn't have a standard frame layout.  I had
not realized that before.  However, even though there's not an ARM ABI
layout, if GCC uses a standard layout, then it would make sense for
_b_f_a(0) to return a pointer to that frame.  (_b_f_a(0) is a GCC
extension, so it can have a GCC-specific definition.)

If even that condition does not hold, then I agree that _b_f_a(0) should
just have undefined behavior on ARM.  We might even consider making it
an error to use it.  We should document in the manual that you can't use
_b_f_a(0) on reliably on some architectures.

If, however, there are plausible semantics we like for _b_f_a(0) on ARM,
then it doesn't seem to me that we should worry terribly much about
pessimizing the code by requiring a hard frame pointer.  Of course, it
would be better not to do so -- but if the only functions affected are
those that actually call _b_f_a(0), I doubt we'd be able to measure a
change in any real-world program.

Richard E. asked what possible uses this function might have.
Obviously, GLIBC's backtrace() function is one, though I guess that's a
weak example, in that we all agree one should really be using unwind
information.  (I still think it's somewhat valid, in that there are a
lot of people building GCC-only applications, and if backtrace() worked
in that case, it would be better than not working at all.)  The other
examples I can think of are also odd hacks; for example, checking for
stack overwrites, manually poking ones own return address pointer, or
manually grabbing saved registers from a caller, or some such.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: Expansion of __builtin_frame_address

[Daniel Jacobowitz]

On Sun, Jun 04, 2006 at 09:54:25AM -0700, Mark Mitchell wrote:
> Richard E. asked what possible uses this function might have.
> Obviously, GLIBC's backtrace() function is one, though I guess that's a
> weak example, in that we all agree one should really be using unwind
> information.

Which there is no plausible way to do for the ARM EABI, due to ARM's
other choices.

-- 
Daniel Jacobowitz
CodeSourcery

Re: Expansion of __builtin_frame_address

[Mark Mitchell]

Daniel Jacobowitz wrote:
> On Sun, Jun 04, 2006 at 09:54:25AM -0700, Mark Mitchell wrote:
>> Richard E. asked what possible uses this function might have.
>> Obviously, GLIBC's backtrace() function is one, though I guess that's a
>> weak example, in that we all agree one should really be using unwind
>> information.
> 
> Which there is no plausible way to do for the ARM EABI, due to ARM's
> other choices.

If one compiled everything with -fexceptions, could you then use the ARM
 ABI EH unwind stuff?  Or, is there just no way to do this in the ARM EABI?

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: Expansion of __builtin_frame_address

[Daniel Jacobowitz]

On Sun, Jun 04, 2006 at 10:29:14AM -0700, Mark Mitchell wrote:
> Daniel Jacobowitz wrote:
> > On Sun, Jun 04, 2006 at 09:54:25AM -0700, Mark Mitchell wrote:
> >> Richard E. asked what possible uses this function might have.
> >> Obviously, GLIBC's backtrace() function is one, though I guess that's a
> >> weak example, in that we all agree one should really be using unwind
> >> information.
> > 
> > Which there is no plausible way to do for the ARM EABI, due to ARM's
> > other choices.
> 
> If one compiled everything with -fexceptions, could you then use the ARM
>  ABI EH unwind stuff?  Or, is there just no way to do this in the ARM EABI?

The DWARF unwinding tables are descriptive; you can interpret them
however necessary, for unwinding or for backtraces.  But the ARM
unwinding tables are more opaque.  You have to call the personality
routines in order to do anything.  I don't believe there's a way to get
runtime backtraces from them, reliably.

It might be possible to implement _Unwind_Backtrace, but it also might
require additional changes similar to those we needed for forced
unwind.

-- 
Daniel Jacobowitz
CodeSourcery

Re: Expansion of __builtin_frame_address

[Mark Mitchell]

Daniel Jacobowitz wrote:
> On Sun, Jun 04, 2006 at 10:29:14AM -0700, Mark Mitchell wrote:
>> Daniel Jacobowitz wrote:
>>> On Sun, Jun 04, 2006 at 09:54:25AM -0700, Mark Mitchell wrote:
>>>> Richard E. asked what possible uses this function might have.
>>>> Obviously, GLIBC's backtrace() function is one, though I guess that's a
>>>> weak example, in that we all agree one should really be using unwind
>>>> information.
>>> Which there is no plausible way to do for the ARM EABI, due to ARM's
>>> other choices.
>> If one compiled everything with -fexceptions, could you then use the ARM
>>  ABI EH unwind stuff?  Or, is there just no way to do this in the ARM EABI?
> 
> The DWARF unwinding tables are descriptive; you can interpret them
> however necessary, for unwinding or for backtraces.  But the ARM
> unwinding tables are more opaque. 

In that case, I guess the only open question is whether _b_f_a(0) has a
sensible GCC-specific meaning, or whether we should just declare it
invalid/undefined on ARM.

Thanks,

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: Expansion of __builtin_frame_address

[Richard Sandiford]

Mark Mitchell <mark@codesourcery.com> writes:
> Richard Sandiford wrote:
>> Mark Mitchell <mark@codesourcery.com> writes:
>>> I'd suggest we leave backtrace() aside, and just talk about
>>> __builtin_frame_address(0), which does have well-defined semantics.
>>> _b_f_a(0) is currently broken on ARM, and we all agree we should fix it.
>> 
>> I don't want to fan the flames here, but I'm not sure either statement
>> is true.  Does __builtin_frame_address(0) really have well-defined
>> semantics on a target for which the ABI does not specify a frame layout?
>> I think that's Richard's point.
>
> Thanks for explaining; after the latest messages from you and Richard
> E., I understand the ARM doesn't have a standard frame layout.  I had
> not realized that before.  However, even though there's not an ARM ABI
> layout, if GCC uses a standard layout, then it would make sense for
> _b_f_a(0) to return a pointer to that frame.  (_b_f_a(0) is a GCC
> extension, so it can have a GCC-specific definition.)
>
> If even that condition does not hold, then I agree that _b_f_a(0) should
> just have undefined behavior on ARM.  We might even consider making it
> an error to use it.  We should document in the manual that you can't use
> _b_f_a(0) on reliably on some architectures.

Sounds like a good idea.

> Richard E. asked what possible uses this function might have.
> Obviously, GLIBC's backtrace() function is one, though I guess that's a
> weak example, in that we all agree one should really be using unwind
> information.  (I still think it's somewhat valid, in that there are a
> lot of people building GCC-only applications, and if backtrace() worked
> in that case, it would be better than not working at all.)  The other
> examples I can think of are also odd hacks; for example, checking for
> stack overwrites, manually poking ones own return address pointer, or
> manually grabbing saved registers from a caller, or some such.

I think it would be better to add builtin-functions that do the things
we think would be useful, and that we're prepared to keep working in
the forseeable future.  Otherwise the knowledge about the exact stack
layout has to be pushed to each user's code, for each architecture that
the user supports.

For example, if all we want in the immediate term is to get a backtrace()
that works on ARM, and we have logic that we think would work, then we
should first make sure that __builtin_return_address(N) implements that
logic for N>0.  To avoid quadrictness in backtrace() itself, we could
add new interfaces, such as a version of __builtin_return_address that
provides the return addresses for a range of call depths.

That probably sounds like a lot of work, but I'm not sure it is.
It might be something we could implement using our existing target hooks.
And it's probably less work than documenting what is and isn't guaranteed
about gcc's frame layout -- and its relation to __builtin_frame_address()
-- for each supported architecture.

Richard