Annoying warning

Annoying warning

[Carlo Wood]

This code snippet, from the STL:

inline int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root)
{
  if (node == 0)
    return 0;
  else {
    int bc = node->color == __rb_tree_black ? 1 : 0;
    if (node == root)
      return bc;
    else
      return bc + __black_count(node->parent, root);
  }
}

causes this warning when compiled with -g -O3 :

/usr/local/egcs/include/g++/stl_tree.h:1045: warning: can't inline call to `int __black_count(struct __rb_tree_node_base *, struct __rb_tree_node_base *)'
/usr/local/egcs/include/g++/stl_tree.h:1053: warning: called from here

Shouldn't this warning be suppressed for a recursive call?

Thanks,

-- 
 Carlo Wood  <carlo@runaway.xs4all.nl>

Re: Annoying warning

[Joe Buck]

> This code snippet, from the STL:
> 
> inline int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root)
> {
    [ a recursive function ]
> }
> 
> causes this warning when compiled with -g -O3 :
> 
> /usr/local/egcs/include/g++/stl_tree.h:1045: warning: can't inline call to `int __black_count(struct __rb_tree_node_base *, struct __rb_tree_node_base *)'
> /usr/local/egcs/include/g++/stl_tree.h:1053: warning: called from here
> 
> Shouldn't this warning be suppressed for a recursive call?

No, the whole point of the warning is to report when an inline operation
can't be performed.

It would be better to either remove the 'inline' or to rewrite the
function into a form that can be inlined (tail recursion):

inline int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root,
			 int black_parent)
{
    if (node == 0)
	return black_parent;
    else {
        int bc = (node->color == __rb_tree_black);
	if (node == root)
	    return bc + black_parent;
	else
	    return __black_count(node->parent, root, bc);
    }
}

inline int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root)
{
    return __black_count(node, root, 0);
}

Re: Annoying warning

[Carlo Wood]

| It would be better to either remove the 'inline' or to rewrite the
| function into a form that can be inlined (tail recursion):
| 
| inline int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root,
| 			 int black_parent)
| {
|     if (node == 0)
| 	return black_parent;
|     else {
|         int bc = (node->color == __rb_tree_black);
| 	if (node == root)
| 	    return bc + black_parent;
| 	else
| 	    return __black_count(node->parent, root, bc);
|     }
| }

I think need to return __black_count(node->parent, root, bc + black_parent) there.

On the other hand, it doesn't seem to increase readability to me.
I'd get rid of the recursion completely and write something like this:

inline int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root)
{
  int count = 0;
  for (; node; node = node->parent)
  {
    if (node->color == __rb_tree_black)
      ++count;
    if (node == root)
      break;
  }
  return count;
}

Perhaps you can forward this to the maintainers of the STL egcs is using?

-- 
 Carlo Wood  <carlo@runaway.xs4all.nl>

Re: Annoying warning

[Joe Buck]

> This code snippet, from the STL:
> 
> inline int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root)
> {
    [ a recursive function ]
> }
> 
> causes this warning when compiled with -g -O3 :
> 
> /usr/local/egcs/include/g++/stl_tree.h:1045: warning: can't inline call to `int __black_count(struct __rb_tree_node_base *, struct __rb_tree_node_base *)'
> /usr/local/egcs/include/g++/stl_tree.h:1053: warning: called from here
> 
> Shouldn't this warning be suppressed for a recursive call?

No, the whole point of the warning is to report when an inline operation
can't be performed.

It would be better to either remove the 'inline' or to rewrite the
function into a form that can be inlined (tail recursion):

inline int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root,
			 int black_parent)
{
    if (node == 0)
	return black_parent;
    else {
        int bc = (node->color == __rb_tree_black);
	if (node == root)
	    return bc + black_parent;
	else
	    return __black_count(node->parent, root, bc);
    }
}

inline int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root)
{
    return __black_count(node, root, 0);
}

Re: Annoying warning

[Carlo Wood]

| It would be better to either remove the 'inline' or to rewrite the
| function into a form that can be inlined (tail recursion):
| 
| inline int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root,
| 			 int black_parent)
| {
|     if (node == 0)
| 	return black_parent;
|     else {
|         int bc = (node->color == __rb_tree_black);
| 	if (node == root)
| 	    return bc + black_parent;
| 	else
| 	    return __black_count(node->parent, root, bc);
|     }
| }

I think need to return __black_count(node->parent, root, bc + black_parent) there.

On the other hand, it doesn't seem to increase readability to me.
I'd get rid of the recursion completely and write something like this:

inline int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root)
{
  int count = 0;
  for (; node; node = node->parent)
  {
    if (node->color == __rb_tree_black)
      ++count;
    if (node == root)
      break;
  }
  return count;
}

Perhaps you can forward this to the maintainers of the STL egcs is using?

-- 
 Carlo Wood  <carlo@runaway.xs4all.nl>

Annoying warning

[Carlo Wood]

This code snippet, from the STL:

inline int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root)
{
  if (node == 0)
    return 0;
  else {
    int bc = node->color == __rb_tree_black ? 1 : 0;
    if (node == root)
      return bc;
    else
      return bc + __black_count(node->parent, root);
  }
}

causes this warning when compiled with -g -O3 :

/usr/local/egcs/include/g++/stl_tree.h:1045: warning: can't inline call to `int __black_count(struct __rb_tree_node_base *, struct __rb_tree_node_base *)'
/usr/local/egcs/include/g++/stl_tree.h:1053: warning: called from here

Shouldn't this warning be suppressed for a recursive call?

Thanks,

-- 
 Carlo Wood  <carlo@runaway.xs4all.nl>

Re: Annoying warning

[Joe Buck]

> 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.

I just confirmed that gcc/egcs correctly transforms and inlines a
tail-recursive function on the Sparc.

Here's my testcase.
---------------------------------
struct node {
    struct node* next;
    int data;
};

inline int last_node(node* p) {
    if (p->next)
	return last_node(p->next);
    else
	return p->data;
}

int call_last_node(node* p) {
    return last_node(p);
}

------------------------

RE: Annoying warning

[Edwards, Phil]

+ -----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.
==========================================

Re: Annoying warning

[Edwards, Phil]

> It would be better to either remove the 'inline' or to rewrite the
> function into a form that can be inlined (tail recursion):

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.  (Which seems
like it would require a really smart optimizer to know when to do that, but
I know nothing about the state of the optimizer art.  I just know that most
of the students I see don't know when to do that, and they're human.  :-)

An iterating version of black_count was also sent to the list.  The patch
and the discussion that led to it were all in mid-to-late November of last
year.  I don't know if or where that list is archived.  I still have the
messages, if anyone is terminally bored.


Phil

RE: Annoying warning

[Edwards, Phil]

+ -----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.
==========================================

Re: Annoying warning

[Joe Buck]

> 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.

I just confirmed that gcc/egcs correctly transforms and inlines a
tail-recursive function on the Sparc.

Here's my testcase.
---------------------------------
struct node {
    struct node* next;
    int data;
};

inline int last_node(node* p) {
    if (p->next)
	return last_node(p->next);
    else
	return p->data;
}

int call_last_node(node* p) {
    return last_node(p);
}

------------------------

Re: Annoying warning

[Edwards, Phil]

> It would be better to either remove the 'inline' or to rewrite the
> function into a form that can be inlined (tail recursion):

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.  (Which seems
like it would require a really smart optimizer to know when to do that, but
I know nothing about the state of the optimizer art.  I just know that most
of the students I see don't know when to do that, and they're human.  :-)

An iterating version of black_count was also sent to the list.  The patch
and the discussion that led to it were all in mid-to-late November of last
year.  I don't know if or where that list is archived.  I still have the
messages, if anyone is terminally bored.


Phil