Problems with pattern rules

[Stepan Kasal]

Hello,
  I think I have encountered a bug in make, but I might be wrong, so
I write here firsk.

I'm using make 3.81, patched.  (3.81-1 from Fedora Core devel)

I encountered a problem with a project (elfutils 0.120); the
situation was like this:

We have something like:

libebl_%.so: libebl_%_pic.a libebl_%.map $(libelf) $(libdw)
        $(LINK) -shared -o $@ -Wl,--whole-archive,$<,--no-whole-archive \
                -Wl,--version-script,$(word 2,$^) \
                -Wl,-z,defs -Wl,--as-needed $(libelf) $(libdw) $(libmudflap)
        $(textrel_check)

libebl_%.map: Makefile
        echo 'ELFUTILS_$(PACKAGE_VERSION) { global: $*_init; local: *; };' > $@

libebl_pic = libebl_i386_pic.a libebl_sh_pic.a libebl_x86_64_pic.a \
             libebl_ia64_pic.a libebl_alpha_pic.a libebl_arm_pic.a \
             libebl_sparc_pic.a libebl_ppc_pic.a libebl_ppc64_pic.a \
             libebl_s390_pic.a
noinst_DATA = $(libebl_pic:_pic.a=.so)

all: $(noinst_DATA)

The scenario does not work as expected:

First, if we run make all twice, the second run rebuilds something.

Second, when we run this with -j4, make often fails: it creates
certain numbers of *.map files (6-9, perhaps) and then starts
building *.so files; when it comes to a case where the *.map file is
missing, the $(LINK) command fails.
(An observation: the `rm' command that removes the *.map files (they
are intermediate) does not include the missing *.map file, so in a
sense, make knows that it was not created.)

If I add a dummy rule mentioning the *.map files, both problems
disappear, which indicates that they are related to intermediate
files.

Now my question:
Is it possible that the Makefile is buggy somehow?  How can I
debug it?

If it is bug in make, which versions of make should I try?
3.81 (unpatched), or a devel version?  Where can I get it.

I know this mail is far from being a useful bug report, but I post it
immediately, instead of waiting for perfectness.

Thank you very much for any help.

Have a nice day,
        Stepan Kasal