This problem crops up when the active version of gcc has been removed (i.e. through emerge --depclean) before a different one has been selected.

>>> Emerging (1 of 2) sys-libs/libselinux-2.0.71
* libselinux-2.0.71.tar.gz RMD160 SHA1 SHA256 size ;-) ...                           [ ok ]
* Package:    sys-libs/libselinux-2.0.71
* Repository: gentoo
* Maintainer: [email protected]
* USE:        elibc_glibc kernel_linux selinux userland_GNU x86
* FEATURES:   sandbox selinux sesandbox
>>> Unpacking source...
>>> Unpacking libselinux-2.0.71.tar.gz to /var/tmp/portage/sys-libs/libselinux-2.0.71/work
>>> Source unpacked in /var/tmp/portage/sys-libs/libselinux-2.0.71/work
>>> Compiling source in /var/tmp/portage/sys-libs/libselinux-2.0.71/work/libselinux-2.0.71 ...
make 'LDFLAGS=-fPIC -Wl,-O1 -Wl,--as-needed' all
make -C src
make[1]: Entering directory `/var/tmp/portage/sys-libs/libselinux-2.0.71/work/libselinux-2.0.71/src'
cc -O2 -march=i686 -pipe -fomit-frame-pointer -mno-tls-direct-seg-refs -fstack-protector-all -I../include -I/usr/include -D_GNU_SOURCE -D_FILE_OFFSET_BITS=64  -mno-tls-direct-seg-refs -c -o avc.o vc.c
gcc-config: error: could not run/locate 'gcc'
make[1]: *** [avc.o] Error 1
make[1]: Leaving directory `/var/tmp/portage/sys-libs/libselinux-2.0.71/work/libselinux-2.0.71/src'
make: *** [all] Error 2
emake failed
* ERROR: sys-libs/libselinux-2.0.71 failed (compile phase):
*   (no error message)
*
* Call stack:
*     ebuild.sh, line  56:  Called src_compile
*   environment, line 4561:  Called die
* The specific snippet of code:
*       emake LDFLAGS="-fPIC ${LDFLAGS}" all || die;
*
* If you need support, post the output of 'emerge --info =sys-libs/libselinux-2.0.71',
* the complete build log and the output of 'emerge -pqv =sys-libs/libselinux-2.0.71'.
* The complete build log is located at '/var/tmp/portage/sys-libs/libselinux-2.0.71/temp/build.log'.
* The ebuild environment file is located at '/var/tmp/portage/sys-libs/libselinux-2.0.71/temp/environment'.
* S: '/var/tmp/portage/sys-libs/libselinux-2.0.71/work/libselinux-2.0.71'
 
>>> Failed to emerge sys-libs/libselinux-2.0.71

Use gcc-config to list the currently installed versions of gcc on your system:

# gcc-config -l
 [1] x86_64-pc-linux-gnu-3.4.6
 [2] x86_64-pc-linux-gnu-3.4.6-hardened
 [3] x86_64-pc-linux-gnu-3.4.6-hardenednopie
 [4] x86_64-pc-linux-gnu-3.4.6-hardenednopiessp
 [5] x86_64-pc-linux-gnu-3.4.6-hardenednossp
 [6] x86_64-pc-linux-gnu-4.4.5

To fix: select the latest or most appropriate version, replacing number with its lists number:

# gcc-config number
# source /etc/profile