<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/105836>105836</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [libLTO, IPGO] Slowdown after b1554fe
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            tools:llvm-link,
            PGO,
            LTO
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          omern1
      </td>
    </tr>
</table>

<pre>
    While building a very large commonly used C++ game engine with `-flto=full` and `-fprofile-instr-generate` we're seeing a very large slowdown in IR link times, causing the total LTO build time to go from 40 minutes to over 2 hours.

A bisection of the issue pointed to commit b1554fe. CC @igorkudrin.

The patch causes the size of the `RAUWWorklist` in the IRLinker to increase considerably and a large number of the entries are descriptors for IPGO counters (`@__profd_*`) which are referenced by the `@llvm.compiler.used` global array, in the case of this program the `@llvm.compiler.used` list grows to 400,000+ elements. Each time RAUW called for one one of the descriptors we end up spending a lot of time iterating over all of the elements of the `@llvm.compiler.used` list to generate a key, and RAUW is called many times:
```
[Inline Frame] llvmLTO.dll!llvm::ConstantAggrKeyType<llvm::ConstantArray>::ConstantAggrKeyType(const llvm::ConstantArray * C, llvm::SmallVectorImpl<llvm::Constant *> & Storage)
llvmLTO.dll!llvm::ConstantUniqueMap<llvm::ConstantArray>::MapInfo::getHashValue(const llvm::ConstantArray * CP)   
llvmLTO.dll!llvm::DenseMapBase<llvm::DenseMap<llvm::ConstantArray *,llvm::detail::DenseSetEmpty,llvm::ConstantUniqueMap<llvm::ConstantArray>::MapInfo,llvm::detail::DenseSetPair<llvm::ConstantArray *>>,llvm::ConstantArray *,llvm::detail::DenseSetEmpty,llvm::ConstantUniqueMap<llvm::ConstantArray>::MapInfo,llvm::detail::DenseSetPair<llvm::ConstantArray *>>::LookupBucketFor<const llvm::ConstantArray *>(const llvm::ConstantArray * const & Val, const llvm::detail::DenseSetPair<llvm::ConstantArray *> * & FoundBucket)     
llvmLTO.dll!llvm::DenseMapBase<llvm::DenseMap<llvm::ConstantArray *,llvm::detail::DenseSetEmpty,llvm::ConstantUniqueMap<llvm::ConstantArray>::MapInfo,llvm::detail::DenseSetPair<llvm::ConstantArray *>>,llvm::ConstantArray *,llvm::detail::DenseSetEmpty,llvm::ConstantUniqueMap<llvm::ConstantArray>::MapInfo,llvm::detail::DenseSetPair<llvm::ConstantArray *>>::LookupBucketFor<const llvm::ConstantArray *>(const llvm::ConstantArray * const & Val, llvm::detail::DenseSetPair<llvm::ConstantArray *> * & FoundBucket)   
llvmLTO.dll!llvm::DenseMapBase<llvm::DenseMap<llvm::ConstantArray *,llvm::detail::DenseSetEmpty,llvm::ConstantUniqueMap<llvm::ConstantArray>::MapInfo,llvm::detail::DenseSetPair<llvm::ConstantArray *>>,llvm::ConstantArray *,llvm::detail::DenseSetEmpty,llvm::ConstantUniqueMap<llvm::ConstantArray>::MapInfo,llvm::detail::DenseSetPair<llvm::ConstantArray *>>::find(const llvm::ConstantArray * Val)  
[Inlined Frame] llvmLTO.dll!llvm::detail::DenseSetImpl<llvm::ConstantArray *,llvm::DenseMap<llvm::ConstantArray *,llvm::detail::DenseSetEmpty,llvm::ConstantUniqueMap<llvm::ConstantArray>::MapInfo,llvm::detail::DenseSetPair<llvm::ConstantArray *>>,llvm::ConstantUniqueMap<llvm::ConstantArray>::MapInfo>::find(const llvm::ConstantArray * V)        
llvmLTO.dll!llvm::ConstantUniqueMap<llvm::ConstantArray>::remove(llvm::ConstantArray * CP)        
llvmLTO.dll!llvm::ConstantUniqueMap<llvm::ConstantArray>::replaceOperandsInPlace(llvm::ArrayRef<llvm::Constant *> Operands, llvm::ConstantArray * CP, llvm::Value * From, llvm::Constant * To, unsigned int NumUpdated, unsigned int OperandNo)     
llvmLTO.dll!llvm::ConstantArray::handleOperandChangeImpl(llvm::Value * From, llvm::Value * To)  
llvmLTO.dll!llvm::Constant::handleOperandChange(llvm::Value * From, llvm::Value * To)   
llvmLTO.dll!llvm::Value::doRAUW(llvm::Value * New, llvm::Value::ReplaceMetadataUses ReplaceMetaUses)    
[Inlined Frame] llvmLTO.dll!`anonymous namespace'::IRLinker::flushRAUWWorklist()   

```

The following is a flamegraph produced by running `llvm-link` on the bitcode, hopefully it makes the situation clearer:

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzsWF1z27oR_TXQy440FETq40EPlmzdeurEHsdJHjNLYkmiAgEWAK1Rf30HoOTIvXLspDcPnXrGlkkAu3v24EDGLjonK020ZNmKZZcD7Hxt7NI0ZPV4kBuxX36tpSLIO6mE1BUgPJLdg0JbERSmaYxWe-gcCVgzvmJ8BRU2BKQrqQl20tfApsmwVN6wyWXZKcWmCaAW_XBrTSkVDaV23g4r0mTRU1iyI8ZnlsAR_SmwU2YnzE6D1HB9D0rqLXjZkGN8DQV2Llj4msAbjwpuHm77DOIi8AYqA6U1DaQJNFJ3nlwYNY9kgUNtOutGLLlkyUX_eQG5dFR4aTSYMnqWznUErZHakwjGgQzpIR9nWVrSCNZrYGkiK2O3nbBSP3P4UBO06Is6og3RawIn_0VH92ya3F98_vrV2K2SzgdCpI4z1_c3Um_JhphSF5bQhZ3QTgqymKt9JBcPTOmuyckevZL2VpIDtASCXGFl6411UBoL13d_3EJhOu3JOmB8zqYJS5Nv38IWiW-MX4QBvoBdLYs6urBUkiVdkIB8f4TN0kSpx2ZUmKaViuwoiCPgr5TJUQFai_uwT4d8ioA_4pMOWmsqi82rvgInUFmzi_uWJgnj6yR8roAUNaS9G8EVFnW_44FKKFApEjFXo6n_7Wk5pWIXWBLQteBa0gfNK-Pj2uBL-iDRMB7lgko9sXuIfLKHP04gCPGgeEDYUqQl7F7EK90RcoN6f9D35CCg4Lv_6V-z1bVW4cRtLDbEsksIcW8ebkdCKcbH4S0YTy7WRjuP2l9Ulf077R_2LbHJ-sx83KfJ1ctWfB5k5-EFW2D8InwprE8WfGpQqS9UeGOvm1adDRzs2OQKGJ_CJ28sVsT4os_ztaQ-a_nPjj5g-4aUPmB7rUvTv1Tk_4au_oKqe2Nid-EssOQVYJekXcCzQvec5uPEy0AjD_xkVpBHqU7MP5G_alq_f7bqv6HitWh3KO0rgIPLq7OA_ueTipM3xmy7dtUVW_IbEwxf1Uok5A2S6lcE2X9BFf-T_YfJL6OP7oPjjem06MG_y_ddvr9Xvu_CfRfuXybcUmrxJhlG8Z0o5OlqJF6_G52D-eI95Tyv_3_6-qU710_v6ptO_a9AstSYx3Dn-wtue78Wv1VY0G1LFrVw1_ouvD7DEw3uqfzhdfno4Pk37_lUTlfEK2-c2VjTnLeO0w9BR9Dp2DIQILWHj13zuRXoSfxp6gDno_kp4g7UhKEatVBHWtY16oriUTwl5kfYv889_ByGF8P_vtB92dEfTxOKvxdCfaTdmUj9432vow_kUaDHz44cnIyF95_8XmTTBLXR-8Z0DjQ25NqozFkf8NiIOJxk1bn6WcuCz5_HO1u3PnVDSqOU2YWyWjpAKBU2VFlsa2itEd2hx2A7rcMaNo119VBJvQ3ltOl7Cbn0hREUOKpNS2Wn1B6khwa3Tz0W32Hs4xSK0Pboeyh8zLJVbs2WNMsuGZ_X3rex4uYbxjeV9HWXh0qe8U3nyA7ReyzqWPIzvkHnKD5Mi2K84MV4OC7nYpiWtBjOKZ8OeTabCS6KLFkkTwXtQCwnYjFZ4ICW4xlPUz5ZLLJBvZwSZjyfZUh8kSTTySwt8lxknE_SPM8n2UAuecLTZM4n43SyyLIRL4t0UeAsJRovxsWcpQk1KNUodiCMrQaxZ7UcJ9l8Mh0ozEm52Pnj3BujQqrfSeWc8TXj_O6P26fnm4f4nF0O7DKuzLvKsTQJ2-2-h_HSq9hSVDKPJuvYXAoC-3Rs3GHpyR6bZYPOquUP2I567_8MW2v-QYVnfBOzCYQfEnpc8n8HAAD__9pwp-k">