Re: empty function optimizations

[Joe Buck <jbuck at racerx dot synopsys dot com>]

> I personally believe that the right fix is in the compiler, which
> should statically determine that instantiations don't depend on the
> some template parameters, and mangle the function names with a
> wildcard.

Certainly we can do that.

But that fix won't accomplish much, because in almost all cases, the
instantiations will appear to depend on the template parameters,
e.g. vector<A*> and vector<B*> will generate the same code, but all
the methods will depend on the type argument.

Consider the following function, for inserting a new element in an
arbitrary position in a vector.  Note that it definitely depends on all of
its arguments (the _Alloc dependency is not obvious, but it determines the
_M_allocate and _M_deallocate member functions), and it is a significant
hunk of code in a program that has vectors of many types.

template <class _Tp, class _Alloc>
void 
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
{
  if (_M_finish != _M_end_of_storage) {
    construct(_M_finish, *(_M_finish - 1));
    ++_M_finish;
    _Tp __x_copy = __x;
    copy_backward(__position, iterator(_M_finish - 2), iterator(_M_finish- 1));
    *__position = __x_copy;
  }
  else {
    const size_type __old_size = size();
    const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
    iterator __new_start(_M_allocate(__len));
    iterator __new_finish(__new_start);
    __STL_TRY {
      __new_finish = uninitialized_copy(iterator(_M_start), __position,
                                        __new_start);
      construct(__new_finish.base(), __x);
      ++__new_finish;
      __new_finish = uninitialized_copy(__position, iterator(_M_finish),
                                        __new_finish);
    }
    __STL_UNWIND((destroy(__new_start,__new_finish), 
                  _M_deallocate(__new_start.base(),__len)));
    destroy(begin(), end());
    _M_deallocate(_M_start, _M_end_of_storage - _M_start);
    _M_start = __new_start.base();
    _M_finish = __new_finish.base();
    _M_end_of_storage = __new_start.base() + __len;
  }
}

Now, for the case where _Tp is a POD, the code, other than _M_allocate
and _M_deallocate, depends only on sizeof(_Tp) (though to know that,
you have to look at the bodies of all called functions).

Now, let's take the case where _Tp is a POD and _Alloc is the default
allocator (a very common case).  In that case, we can write one standard
function to do this operation for any _Tp.  But it has to be done
by the library developer, the compiler has no hope of doing the job.

> The tricky part, of course, is to define the exact mechanism for
> determining independence from template parameters.

It could probably be done only for leaf functions (or functions that
are leaves after inlining).