RE: Annoying warning

["Edwards, Phil" <pedwards@ball.com>]

+ -----Original Message-----
+ From: Joe Buck [ mailto:jbuck@Synopsys.COM ]
+ Subject: Re: Annoying warning
+ 
+ > I mentioned this to the libstdc++-v3 list some time back.  
+ The solution then
+ > was to simply remove the 'inline' since (according to the 
+ list) the egcs
+ > optimizer doesn't know how to turn tail recursion into a loop. 
+ 
+ That's incorrect: gcc does know how to eliminate tail 
+ recursion and has
+ for a long time.  RMS put that one in years ago: anyone from 
+ MIT, where
+ Scheme rules, wouldn't tolerate a compiler that can't handle 
+ tail recursion.

Hey, all I know is how to misquote from the libstdc++ list archives.  I just
work here.  Do you want fries with that?  :-)

+ I just confirmed that gcc/egcs correctly transforms and inlines a
+ tail-recursive function on the Sparc.
+ 
+ Here's my testcase.
[snip]

Worked for me.  If it hasn't already been done (I don't have the libstdc++
snapshot on this machine), it seems like the recursive fn should be
rewritten as a loop, and the 'inline' keyword re-added.  EGCS groks
tail-recursion in general, but it isn't doing so in /this/ one particular
case, for whatever reason.

Nathan Meyers sent one non-recursive implementation to libstdc++; I'll quote
from his message here:

==========================================
G++ *should* be able to inline it.  It's tail-recursive,
so is easily turned into a loop.  (This is stl/bits/stl_tree.h,
function __black_count().)

If we can't get g++ to inline it as is, we should go ahead and
manually turn it into a loop ourselves.  Something like

***
  __sum += (__node->_M_color == _S_rb_tree_black) ? 1 : 0;
  return (__node == __root) ?
    __sum : __black_count(__node->_M_parent, __root, __sum);
---
  do {
    __sum += (__node->_M_color == _S_rb_tree_black) ? 1 : 0;
    if (__node == __root) break;
    __node = __node->_M_parent;
  } while (1);
  return __sum;

And, of course, put the inline back in.

In that case there's no need for the __sum argument; it could 
be a local variable instead, though that shouldn't make any 
difference if the function actually gets inlined.
==========================================