Ubuntu 18, gcc-9 failed to link tbb library for execution policy in standard library – Debian

I am trying to compile a C++17 code with g++-9 that uses execution policy in Ubuntu 18.04.5 LTS. I build and installed TBB 2020.2 with GCC-9 manually as it is not available by default for Ubuntu 18.

When I call a function that uses execution policy with parameters std::execution::seq or std::exectuion::unseq everything is fine. But when I call the same functions with parameters std::execution::par or std::execution::par_unseq it fails to link TBB. Note that the same code compiles and works without any issues in Debian 10.

My CMake is as follow and it prints the correct version of TBB (2020.2) that I want to link.

find_package(TBB REQUIRED)
if (TBB_VERSION_MAJOR VERSION_LESS "2018")
    message(FATAL_ERROR "Require tbb 2018 or higher.")
endif()
message(STATUS "TBB: ${TBB_VERSION}")
...
add_executable(${PROJECT_NAME} ${SOURCES})
target_link_libraries(${PROJECT_NAME} PUBLIC ${TBB_IMPORTED_TARGETS})

EDIT:
Per S.M. advice on the comment using MAKE_VERBOSE_MAKEFILE I figured out there is no linking to TBB:

[ 75%] Linking CXX executable serialize
/usr/bin/cmake -E cmake_link_script CMakeFiles/serialize.dir/link.txt --verbose=1
/usr/bin/g++-9  -Wall -Wextra -Werror -fopenmp -ftree-vectorize -march=native -msse3 -O4 -DNDEBUG   CMakeFiles/serialize.dir/serialize.cpp.o  -o serialize 
CMakeFiles/serialize.dir/build.make:97: recipe for target 'serialize' failed
make[2]: Leaving directory '/home/user/build-tresa'

Also again I printed the TBB_IMPORTED_TARGETS variable in the CMake and it looks like that it is empty.
replacing TBB_IMPORTED_TARGETS with TBB in target_link_libaries also didn’t help.
It is very strange that CMake prints the TBB version but there are no TBB_IMPORTED_TARGETS and it doesn’t link any tbb shared object to executable.

Following is the compiler message messages:

CMakeFiles/serialize.dir/serialize.cpp.o: In function `__pstl::__par_backend::__merge_task<std::pair<unsigned int, unsigned int>*, std::pair<unsigned int, unsigned int>*, __gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > >, read<unsigned int, unsigned int>(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&)::{lambda(auto:1 const&, auto:2 const&)#1}, __pstl::__par_backend::__serial_destroy, __pstl::__par_backend::__serial_move_merge<__pstl::__par_backend::__stable_sort_task<__gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > >, std::pair<unsigned int, unsigned int>*, {lambda(auto:1 const&, auto:2 const&)#1}, __pstl::__internal::__pattern_sort<__pstl::execution::v1::parallel_policy const&, __gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > >, {lambda(auto:1 const&, auto:2 const&)#1}, std::integral_constant<bool, false> >(__pstl::execution::v1::parallel_policy const&, __gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > >, __gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > >, {lambda(auto:1 const&, auto:2 const&)#1}, std::integral_constant<bool, false>, __pstl::execution::v1::parallel_policy const&<bool, true>, std::integral_constant<bool, false>)::{lambda()#1}::operator()() const::{lambda(__gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > >, __gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > >, {lambda(auto:1 const&, auto:2 const&)#1})#1}>::execute()::{lambda(std::pair<unsigned int, unsigned int>*, __gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > >)#1}, {lambda()#1}::execute()::{lambda(std::pair<unsigned int, unsigned int>*, std::pair<unsigned int, unsigned int>*, __gnu_cxx::__normal_iterator<std::pair<unsigned int, unsigned int>*, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > >)#2}> >::execute()':

...

CMakeFiles/tresa.dir/main.cpp.o: In function `std::vector<unsigned int, std::allocator<unsigned int> > nonzero<unsigned int, unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> >)':
main.cpp:(.text._Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE[_Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE]+0x153): undefined reference to `tbb::internal::allocate_via_handler_v3(unsigned long)'
main.cpp:(.text._Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE[_Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE]+0x1d1): undefined reference to `tbb::interface7::internal::isolate_within_arena(tbb::interface7::internal::delegate_base&, long)'
main.cpp:(.text._Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE[_Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE]+0x200): undefined reference to `tbb::internal::allocate_via_handler_v3(unsigned long)'
main.cpp:(.text._Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE[_Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE]+0x297): undefined reference to `tbb::interface7::internal::isolate_within_arena(tbb::interface7::internal::delegate_base&, long)'
main.cpp:(.text._Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE[_Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE]+0x2e8): undefined reference to `tbb::interface7::internal::isolate_within_arena(tbb::interface7::internal::delegate_base&, long)'
main.cpp:(.text._Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE[_Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE]+0x2f9): undefined reference to `tbb::internal::deallocate_via_handler_v3(void*)'
main.cpp:(.text._Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE[_Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE]+0x301): undefined reference to `tbb::internal::deallocate_via_handler_v3(void*)'
main.cpp:(.text._Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE[_Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE]+0x43d): undefined reference to `tbb::internal::deallocate_via_handler_v3(void*)'
main.cpp:(.text._Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE[_Z7nonzeroIjjESt6vectorIT_SaIS1_EERKS3_S0_IT0_SaIS6_EE]+0x491): undefined reference to `tbb::internal::deallocate_via_handler_v3(void*)'
CMakeFiles/tresa.dir/main.cpp.o: In function `std::tuple<std::vector<long long, std::allocator<long long> >, std::vector<unsigned int, std::allocator<unsigned int> > > mnge<unsigned int, unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)':
main.cpp:(.text._Z12multi_arangeIjjESt5tupleIJSt6vectorIxSaIxEES1_IT_SaIS4_EEEERKS6_RKS1_IT0_SaISA_EE[_Z12multi_arangeIjjESt5tupleIJSt6vectorIxSaIxEES1_IT_SaIS4_EEEERKS6_RKS1_IT0_SaISA_EE]+0x220): undefined reference to `tbb::interface7::internal::isolate_within_arena(tbb::interface7::internal::delegate_base&, long)'
main.cpp:(.text._Z12multi_arangeIjjESt5tupleIJSt6vectorIxSaIxEES1_IT_SaIS4_EEEERKS6_RKS1_IT0_SaISA_EE[_Z12multi_arangeIjjESt5tupleIJSt6vectorIxSaIxEES1_IT_SaIS4_EEEERKS6_RKS1_IT0_SaISA_EE]+0x41b): undefined reference to `tbb::interface7::internal::isolate_within_arena(tbb::interface7::internal::delegate_base&, long)'
CMakeFiles/tresa.dir/main.cpp.o: In function `_ZN3tbb15parallel_invokeIZN6__pstl13__par_backend9__upsweepIllZZNS1_10__internal17__remove_elementsIRKNS1_9execution2v115parallel_policyEN9__gnu_cxx17__normal_iteratorIPjSt6vectorIjSaIjEEEEZNS4_19__pattern_remove_ifISA_SH_Z7nonzeroIjjESE_IT_SaISK_EERKSM_SE_IT0_SaISP_EEEUlRjE_St17integral_constantIbLb0EEEESP_OSK_SP_SP_T1_T2_SU_IbLb1EEEUlPbS10_SH_E_SV_EESP_SW_SP_SP_SX_SY_ENKUlvE_clEvEUlllE1_St4plusIlEEEvSK_SK_SK_PSP_SK_SX_SY_EUlvE_ZNS3_IllS13_S15_EEvSK_SK_SK_S16_SK_SX_SY_EUlvE0_EEvRKSK_RKSP_RNS_18task_group_contextE':

...


CMakeFiles/tresa.dir/main.cpp.o:(.data.rel.ro._ZTIN6__pstl13__par_backend12__merge_taskIN9__gnu_cxx17__normal_iteratorIPSt4pairIjjESt6vectorIS5_SaIS5_EEEESA_S6_Z8readIjjE7graph_tIT_T0_ERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEEEUlRKSD_RKSE_E_NS0_14__binary_no_opENS0_19__serial_move_mergeIZNS0_18__stable_sort_taskISA_S6_SS_ZZNS_10__internal14__pattern_sortIRKNS_9execution2v115parallel_policyESA_SS_St17integral_constantIbLb0EEEEvOSD_SE_SE_T1_T2_S13_IbLb1EES18_ENKUlvE_clEvEUlSA_SA_SS_E_E7executeEvEUlSA_S6_E1_ZNS1B_7executeEvEUlSA_SA_S6_E2_EEEE[_ZTIN6__pstl13__par_backend12__merge_taskIN9__gnu_cxx17__normal_iteratorIPSt4pairIjjESt6vectorIS5_SaIS5_EEEESA_S6_Z8readIjjE7graph_tIT_T0_ERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEEEUlRKSD_RKSE_E_NS0_14__binary_no_opENS0_19__serial_move_mergeIZNS0_18__stable_sort_taskISA_S6_SS_ZZNS_10__internal14__pattern_sortIRKNS_9execution2v115parallel_policyESA_SS_St17integral_constantIbLb0EEEEvOSD_SE_SE_T1_T2_S13_IbLb1EES18_ENKUlvE_clEvEUlSA_SA_SS_E_E7executeEvEUlSA_S6_E1_ZNS1B_7executeEvEUlSA_SA_S6_E2_EEEE]+0x10): undefined reference to `typeinfo for tbb::task'

...


CMakeFiles/tresa.dir/main.cpp.o:(.data.rel.ro._ZTIN3tbb10interface98internal9start_forINS_13blocked_rangeIPjEEN6__pstl13__par_backend19__parallel_for_bodyIS4_ZZNS6_10__internal17__remove_elementsIRKNS6_9execution2v115parallel_policyEN9__gnu_cxx17__normal_iteratorIS4_St6vectorIjSaIjEEEEZNS9_19__pattern_remove_ifISF_SL_Z7nonzeroIjjESI_IT_SaISO_EERKSQ_SI_IT0_SaIST_EEEUlRjE_St17integral_constantIbLb0EEEEST_OSO_ST_ST_T1_T2_SY_IbLb1EEEUlPbS14_SL_E_SZ_EEST_S10_ST_ST_S11_S12_ENKUlvE_clEvEUlS4_S4_E4_EEKNS_16auto_partitionerEEE[_ZTIN3tbb10interface98internal9start_forINS_13blocked_rangeIPjEEN6__pstl13__par_backend19__parallel_for_bodyIS4_ZZNS6_10__internal17__remove_elementsIRKNS6_9execution2v115parallel_policyEN9__gnu_cxx17__normal_iteratorIS4_St6vectorIjSaIjEEEEZNS9_19__pattern_remove_ifISF_SL_Z7nonzeroIjjESI_IT_SaISO_EERKSQ_SI_IT0_SaIST_EEEUlRjE_St17integral_constantIbLb0EEEEST_OSO_ST_ST_T1_T2_SY_IbLb1EEEUlPbS14_SL_E_SZ_EEST_S10_ST_ST_S11_S12_ENKUlvE_clEvEUlS4_S4_E4_EEKNS_16auto_partitionerEEE]+0x10): more undefined references to `typeinfo for tbb::task' follow
CMakeFiles/tresa.dir/main.cpp.o:(.data.rel.ro._ZTVN3tbb10interface98internal9flag_taskE[_ZTVN3tbb10interface98internal9flag_taskE]+0x28): undefined reference to `tbb::task::note_affinity(unsigned short)'
CMakeFiles/tresa.dir/main.cpp.o:(.data.rel.ro._ZTVN3tbb8internal22parallel_invoke_helperE[_ZTVN3tbb8internal22parallel_invoke_helperE]+0x28): undefined reference to `tbb::task::note_affinity(unsigned short)'
CMakeFiles/tresa.dir/main.cpp.o:(.data.rel.ro._ZTVN6__pstl13__par_backend18__stable_sort_taskIN9__gnu_cxx17__normal_iteratorIPSt4pairIjjESt6vectorIS5_SaIS5_EEEES6_Z8readIjjE7graph_tIT_T0_ERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEEEUlRKSD_RKSE_E_ZZNS_10__internal14__pattern_sortIRKNS_9execution2v115parallel_policyESA_SS_St17integral_constantIbLb0EEEEvOSD_SE_SE_T1_T2_S10_IbLb1EES15_ENKUlvE_clEvEUlSA_SA_SS_E_EE[_ZTVN6__pstl13__par_backend18__stable_sort_taskIN9__gnu_cxx17__normal_iteratorIPSt4pairIjjESt6vectorIS5_SaIS5_EEEES6_Z8readIjjE7graph_tIT_T0_ERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEEEUlRKSD_RKSE_E_ZZNS_10__internal14__pattern_sortIRKNS_9execution2v115parallel_policyESA_SS_St17integral_constantIbLb0EEEEvOSD_SE_SE_T1_T2_S10_IbLb1EES15_ENKUlvE_clEvEUlSA_SA_SS_E_EE]+0x28): undefined reference to `tbb::task::note_affinity(unsigned short)'

...


CMakeFiles/tresa.dir/main.cpp.o:(.data.rel.ro._ZTVN3tbb8internal9final_sumINS_13blocked_rangeIlEEN6__pstl13__par_backend17__trans_scan_bodyIlZZNS4_10__internal24__pattern_transform_scanIRKNS4_9execution2v115parallel_policyEN9__gnu_cxx17__normal_iteratorIPKjSt6vectorIjSaIjEEEENSF_IPjSK_EENS7_7__no_opEjSt4plusIjESt17integral_constantIbLb1EESR_IbLb0EEEENSt9enable_ifIXntsrSt17is_floating_pointIT3_E5valueET1_E4typeEOT_T0_S13_SY_T2_SW_T4_T5_T6_SS_ENKUlvE_clEvEUllE_jSQ_ZZNS8_ISD_SL_SN_SO_jSQ_SS_ST_EES10_S12_S13_S13_SY_S14_SW_S15_S16_S17_SS_ENKS18_clEvEUllljE0_ZZNS8_ISD_SL_SN_SO_jSQ_SS_ST_EES10_S12_S13_S13_SY_S14_SW_S15_S16_S17_SS_ENKS18_clEvEUllljE1_EEEE[_ZTVN3tbb8internal9final_sumINS_13blocked_rangeIlEEN6__pstl13__par_backend17__trans_scan_bodyIlZZNS4_10__internal24__pattern_transform_scanIRKNS4_9execution2v115parallel_policyEN9__gnu_cxx17__normal_iteratorIPKjSt6vectorIjSaIjEEEENSF_IPjSK_EENS7_7__no_opEjSt4plusIjESt17integral_constantIbLb1EESR_IbLb0EEEENSt9enable_ifIXntsrSt17is_floating_pointIT3_E5valueET1_E4typeEOT_T0_S13_SY_T2_SW_T4_T5_T6_SS_ENKUlvE_clEvEUllE_jSQ_ZZNS8_ISD_SL_SN_SO_jSQ_SS_ST_EES10_S12_S13_S13_SY_S14_SW_S15_S16_S17_SS_ENKS18_clEvEUllljE0_ZZNS8_ISD_SL_SN_SO_jSQ_SS_ST_EES10_S12_S13_S13_SY_S14_SW_S15_S16_S17_SS_ENKS18_clEvEUllljE1_EEEE]+0x28): more undefined references to `tbb::task::note_affinity(unsigned short)' follow
collect2: error: ld returned 1 exit status
CMakeFiles/tresa.dir/build.make:94: recipe for target 'tresa' failed
make[2]: *** [tresa] Error 1
CMakeFiles/Makefile2:67: recipe for target 'CMakeFiles/tresa.dir/all' failed
make[1]: *** [CMakeFiles/tresa.dir/all] Error 2
Makefile:83: recipe for target 'all' failed
make: *** [all] Error 2