I want to altinstall 3.6 with LTO+PGO optimizations, so:

./configure --enable-shared --enable-optimizations --prefix=$HOME/.local LDFLAGS=-Wl,-rpath=$HOME/.local/lib
make

(./configure arguments refer to issue #27685)

But I get in trouble when running compiled python to generate posix vars:

...
gcc -pthread -shared -Wl,-rpath=/home/halfcoder/.local/lib -fprofile-generate  -Wl,--no-as-needed -o libpython3.so -Wl,-hlibpython3.so libpython3.6m.so
gcc -pthread -Wl,-rpath=/home/halfcoder/.local/lib -fprofile-generate  -Xlinker -export-dynamic -o python Programs/python.o -L. -lpython3.6m -lpthread -ldl  -lutil   -lm
LD_LIBRARY_PATH=/home/halfcoder/.local/src/Python-3.6.0-optmiz ./python -E -S -m sysconfig --generate-posix-vars ;\
if test $? -ne 0 ; then \
        echo "generate-posix-vars failed" ; \
        rm -f ./pybuilddir.txt ; \
        exit 1 ; \
fi
./python: symbol lookup error: ./python: undefined symbol: __gcov_indirect_call_profiler
generate-posix-vars failed
make[2]: *** [pybuilddir.txt] Error 1
make[2]: Leaving directory `/home/halfcoder/.local/src/Python-3.6.0-optmiz'
make[1]: *** [build_all_generate_profile] Error 2
make[1]: Leaving directory `/home/halfcoder/.local/src/Python-3.6.0-optmiz'
make: *** [profile-opt] Error 2

gcc information below:

Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-redhat-linux/4.8.5/lto-wrapper
Target: x86_64-redhat-linux
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --with-bugurl=http://bugzilla.redhat.com/bugzilla --enable-bootstrap --enable-shared --enable-threads=posix --enable-checking=release --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-gnu-unique-object --enable-linker-build-id --with-linker-hash-style=gnu --enable-languages=c,c++,objc,obj-c++,java,fortran,ada,go,lto --enable-plugin --enable-initfini-array --disable-libgcj --with-isl=/builddir/build/BUILD/gcc-4.8.5-20150702/obj-x86_64-redhat-linux/isl-install --with-cloog=/builddir/build/BUILD/gcc-4.8.5-20150702/obj-x86_64-redhat-linux/cloog-install --enable-gnu-indirect-function --with-tune=generic --with-arch_32=x86-64 --build=x86_64-redhat-linux
Thread model: posix
gcc version 4.8.5 20150623 (Red Hat 4.8.5-11) (GCC)

For the record, --enable-shared generally produces slower builds than by default.  The slowdown depends on the platform, but it's noticeable on x86-64 and much more on ARM.

I have the same error when building 3.6.4, however not exactly with the same options. Some context first:
$ lsb_release -d; lscpu |head -1
Description:        Ubuntu 14.04.5 LTS
Architecture:          x86_64
$ gcc --version
gcc (Ubuntu 4.8.4-2ubuntu1~14.04.4) 4.8.4

I'm careful to start from a freshly untarred source tree. 

This configuration builds a working installation:
$ ./configure --prefix=$PYTHON --enable-optimizations --enable-shared LDFLAGS="-Wl,-rpath=$PYTHON/lib -Wl,-Bsymbolic-functions -Wl,-z,relro" --with-computed-gotos --with-system-ffi --with-fpectl --with-system-libmpdec
$ make profile-opt

However, I get the reported error when CFLAGS="-mtune=core-avx2  -march=core-avx2" is added. 

This set of options works fine without --enable-shared, i.e. this is what I am using for static builds:
$ ./configure --prefix=$PYTHON --enable-optimizations LDFLAGS="-Wl,-z,relro" --with-computed-gotos --with-system-ffi --with-fpectl --with-system-libmpdec CFLAGS="-mtune=core-avx2 -march=core-avx2 -Wformat -Werror=format-security"

Note, with the following configuration (-mtune without -march), compilation just blocks on Objects/memoryobject.c (ie, gcc never completes):
$ ./configure --prefix=$PYTHON --enable-optimizations --enable-shared LDFLAGS="-Wl,-rpath=$PYTHON/lib -Wl,-Bsymbolic-functions -Wl,-z,relro" --with-computed-gotos --with-system-ffi --with-fpectl --with-system-libmpdec CFLAGS="-mtune=core-avx2  -Werror=format-security"
$ make profile-opt

I was having the same problem, and I just found out what it was: Because of -Wl,-rpath=..., this path gets baked into the binary, and LD_LIBRARY_PATH is ignored. So if you have a previous build lying around there, it will mess up the build.