Description of problem:
I'm seeing fatal "unimplemented insn" errors when attempting to run gcc under valgrind on s390x EL7:

vex s390->IR: unimplemented insn: B9E1 0033
==360== valgrind: Unrecognised instruction at address 0x419a028.
==360==    at 0x419A028: bitmap_count_bits(bitmap_head const*) (bitmap.c:660)
(snip)

Connecting to valgrind from gdb shows it failing consistently here:

Dump of assembler code for function bitmap_count_bits(bitmap_head const*):
   0x000000000419a008 <+0>:	stg	%r11,88(%r15)
   0x000000000419a00e <+6>:	ltg	%r11,8(%r2)
   0x000000000419a014 <+12>:	lghi	%r2,0
   0x000000000419a018 <+16>:	je	0x419a08a <bitmap_count_bits(bitmap_head const*)+130>
   0x000000000419a01c <+20>:	lg	%r3,24(%r11)
   0x000000000419a022 <+26>:	lg	%r1,32(%r11)
   0x000000000419a028 <+32>:	popcnt	%r3,%r3
=> 0x000000000419a02c <+36>:	popcnt	%r1,%r1
   0x000000000419a030 <+40>:	sllg	%r5,%r3,32
   0x000000000419a036 <+46>:	sllg	%r4,%r1,32
   0x000000000419a03c <+52>:	agr	%r3,%r5
   0x000000000419a040 <+56>:	agr	%r1,%r4
   0x000000000419a044 <+60>:	sllg	%r5,%r3,16
   0x000000000419a04a <+66>:	sllg	%r4,%r1,16
   0x000000000419a050 <+72>:	agr	%r3,%r5
   0x000000000419a054 <+76>:	agr	%r1,%r4
   0x000000000419a058 <+80>:	sllg	%r5,%r3,8
   0x000000000419a05e <+86>:	sllg	%r4,%r1,8
   0x000000000419a064 <+92>:	agr	%r3,%r5
   0x000000000419a068 <+96>:	agr	%r1,%r4
   0x000000000419a06c <+100>:	srlg	%r3,%r3,56
   0x000000000419a072 <+106>:	srlg	%r1,%r1,56
   0x000000000419a078 <+112>:	agr	%r1,%r3
   0x000000000419a07c <+116>:	agr	%r2,%r1
   0x000000000419a080 <+120>:	ltg	%r11,0(%r11)
   0x000000000419a086 <+126>:	jne	0x419a01c <bitmap_count_bits(bitmap_head const*)+20>
   0x000000000419a08a <+130>:	lg	%r11,88(%r15)
   0x000000000419a090 <+136>:	br	%r14
End of assembler dump.


Version-Release number of selected component (if applicable):
valgrind-3.10.0-16.el7.s390x
gcc-4.8.3-9.el7.s390x


How reproducible:
100%

Steps to Reproduce:
A more minimal reproducer:
$ cat popcnt.c

int main (int argc, const char **argv)
{
  return __builtin_popcountl ((long)argc);
}

$ gcc popcnt.c
$ valgrind ./a.out


Actual results:

==507== Memcheck, a memory error detector
==507== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==507== Using Valgrind-3.10.0 and LibVEX; rerun with -h for copyright info
==507== Command: ./a.out
==507== 
vex s390->IR: unimplemented insn: B9E1 0011
==507== valgrind: Unrecognised instruction at address 0x80000564.
==507==    at 0x80000564: main (in /home/dmalcolm/gcc-bugfixing/src/a.out)
==507== Your program just tried to execute an instruction that Valgrind
==507== did not recognise.  There are two possible reasons for this.
==507== 1. Your program has a bug and erroneously jumped to a non-code
==507==    location.  If you are running Memcheck and you just saw a
==507==    warning about a bad jump, it's probably your program's fault.
==507== 2. The instruction is legitimate but Valgrind doesn't handle it,
==507==    i.e. it's Valgrind's fault.  If you think this is the case or
==507==    you are not sure, please let us know and we'll try to fix it.
==507== Either way, Valgrind will now raise a SIGILL signal which will
==507== probably kill your program.
==507== 
==507== Process terminating with default action of signal 4 (SIGILL)
==507==  Illegal opcode at address 0x80000564
==507==    at 0x80000564: main (in /home/dmalcolm/gcc-bugfixing/src/a.out)
==507== 
==507== HEAP SUMMARY:
==507==     in use at exit: 0 bytes in 0 blocks
==507==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==507== 
==507== All heap blocks were freed -- no leaks are possible
==507== 
==507== For counts of detected and suppressed errors, rerun with: -v
==507== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Illegal instruction (core dumped)

Expected results:

Successful execution of the test binary.

Additional info:

Seen when trying to run gcc under valgrind; which gave me this error:
  vex s390->IR: unimplemented insn: B9E1 0033
(is this a different addressing mode? or just different registers?)

FWIW https://patchwork.ozlabs.org/patch/187671/ has a patch for qemu for implementing popcnt on s390x, and this confirms 0xb9e1 as the first 2 bytes of the opcode.