In the early days there was prelink as part of maemo. It disappeared in the n810 distribution ranges. I noticed that there is no armel deb in debian for prelink, but there were murmurs of folks hacking it to work. Push finally came to shove, and as I like C++ many of my apps on maemo have quite a few symbols that need to be resolved before the app can run.
The long story short, prelink_0.0.20090311 is up at my repo. Use at your own risk, if your device breaks you get to keep both pieces etc etc.
Initial benchmarking: for an app that uses a few libraries, is C++, and has quite a few symbols that the dynamic linker has to attend to. For a complete run before it was 5.2 seconds on a warm start, with prelink of the binary it is 2.5 seconds. Considering that in that 2.5 the app itself has to completely run, there was a huge amount of time spent, err wasted, in the dynamic linker.
Of course, if I can get hidden symbols to work too then that 2.5 might drop back to 1.5-2 seconds. But for hidden symbols you have to either wrap things in pragmas or declare each function and class as exposed or not, so for a large library its quite intrusive. But the prelink is a huge gain for no code changes, so far at least. YMMV.
It's a touch ironic that Nokia recommends using prelink for embedded devices. But that is for qtopia... maybe for the next distro prelink will reappear in the default installation.