src/backend/jit/llvm/llvmjit_inline.cpp

   1 /*-------------------------------------------------------------------------
   2  *
   3  * llvmjit_inline.cpp
   4  *        Cross module inlining suitable for postgres' JIT
   5  *
   6  * The inliner iterates over external functions referenced from the passed
   7  * module and attempts to inline those.  It does so by utilizing pre-built
   8  * indexes over both postgres core code and extension modules.  When a match
   9  * for an external function is found - not guaranteed! - the index will then
  10  * be used to judge their instruction count / inline worthiness. After doing
  11  * so for all external functions, all the referenced functions (and
  12  * prerequisites) will be imported.
  13  *
  14  * Copyright (c) 2016-2025, PostgreSQL Global Development Group
  15  *
  16  * IDENTIFICATION
  17  *        src/backend/lib/llvmjit/llvmjit_inline.cpp
  18  *
  19  *-------------------------------------------------------------------------
  20  */
  21
  22 extern "C"
  23 {
  24 #include "postgres.h"
  25 }
  26
  27 #include "jit/llvmjit.h"
  28
  29 extern "C"
  30 {
  31 #include <fcntl.h>
  32 #include <sys/mman.h>
  33 #include <sys/stat.h>
  34 #include <sys/types.h>
  35 #include <unistd.h>
  36
  37 #include "common/string.h"
  38 #include "miscadmin.h"
  39 #include "storage/fd.h"
  40 }
  41
  42 #include <llvm-c/Core.h>
  43 #include <llvm-c/BitReader.h>
  44
  45 /* Avoid macro clash with LLVM's C++ headers */
  46 #undef Min
  47
  48 #include <llvm/ADT/SetVector.h>
  49 #include <llvm/ADT/StringSet.h>
  50 #include <llvm/ADT/StringMap.h>
  51 #include <llvm/Analysis/ModuleSummaryAnalysis.h>
  52 #include <llvm/Bitcode/BitcodeReader.h>
  53 #include <llvm/IR/Attributes.h>
  54 #include <llvm/IR/DebugInfo.h>
  55 #include <llvm/IR/IntrinsicInst.h>
  56 #include <llvm/IR/IRBuilder.h>
  57 #include <llvm/IR/ModuleSummaryIndex.h>
  58 #include <llvm/Linker/IRMover.h>
  59 #include <llvm/Support/ManagedStatic.h>
  60 #include <llvm/Support/MemoryBuffer.h>
  61
  62
  63 /*
  64  * Type used to represent modules InlineWorkListItem's subject is searched for
  65  * in.
  66  */
  67 typedef llvm::SmallVector<llvm::ModuleSummaryIndex *, 2> InlineSearchPath;
  68
  69 /*
  70  * Item in queue of to-be-checked symbols and corresponding queue.
  71  */
  72 typedef struct InlineWorkListItem
  73 {
  74         llvm::StringRef symbolName;
  75         llvm::SmallVector<llvm::ModuleSummaryIndex *, 2> searchpath;
  76 } InlineWorkListItem;
  77 typedef llvm::SmallVector<InlineWorkListItem, 128> InlineWorkList;
  78
  79 /*
  80  * Information about symbols processed during inlining. Used to prevent
  81  * repeated searches and provide additional information.
  82  */
  83 typedef struct FunctionInlineState
  84 {
  85         int costLimit;
  86         bool processed;
  87         bool inlined;
  88         bool allowReconsidering;
  89 } FunctionInlineState;
  90 typedef llvm::StringMap<FunctionInlineState> FunctionInlineStates;
  91
  92 /*
  93  * Map of modules that should be inlined, with a list of the to-be inlined
  94  * symbols.
  95  */
  96 typedef llvm::StringMap<llvm::StringSet<> > ImportMapTy;
  97
  98
  99 const float inline_cost_decay_factor = 0.5;
 100 const int inline_initial_cost = 150;
 101
 102 /*
 103  * These are managed statics so LLVM knows to deallocate them during an
 104  * LLVMShutdown(), rather than after (which'd cause crashes).
 105  */
 106 typedef llvm::StringMap<std::unique_ptr<llvm::Module> > ModuleCache;
 107 llvm::ManagedStatic<ModuleCache> module_cache;
 108 typedef llvm::StringMap<std::unique_ptr<llvm::ModuleSummaryIndex> > SummaryCache;
 109 llvm::ManagedStatic<SummaryCache> summary_cache;
 110
 111
 112 static std::unique_ptr<ImportMapTy> llvm_build_inline_plan(LLVMContextRef lc, llvm::Module *mod);
 113 static void llvm_execute_inline_plan(llvm::Module *mod,
 114                                                                          ImportMapTy *globalsToInline);
 115
 116 static llvm::Module* load_module_cached(LLVMContextRef c, llvm::StringRef modPath);
 117 static std::unique_ptr<llvm::Module> load_module(LLVMContextRef c, llvm::StringRef Identifier);
 118 static std::unique_ptr<llvm::ModuleSummaryIndex> llvm_load_summary(llvm::StringRef path);
 119
 120
 121 static llvm::Function* create_redirection_function(std::unique_ptr<llvm::Module> &importMod,
 122                                                                                                    llvm::Function *F,
 123                                                                                                    llvm::StringRef Name);
 124
 125 static bool function_inlinable(llvm::Function &F,
 126                                                            int threshold,
 127                                                            FunctionInlineStates &functionState,
 128                                                            InlineWorkList &worklist,
 129                                                            InlineSearchPath &searchpath,
 130                                                            llvm::SmallPtrSet<const llvm::Function *, 8> &visitedFunctions,
 131                                                            int &running_instcount,
 132                                                            llvm::StringSet<> &importVars);
 133 static void function_references(llvm::Function &F,
 134                                                                 int &running_instcount,
 135                                                                 llvm::SmallPtrSet<llvm::GlobalVariable *, 8> &referencedVars,
 136                                                                 llvm::SmallPtrSet<llvm::Function *, 8> &referencedFunctions);
 137
 138 static void add_module_to_inline_search_path(InlineSearchPath& path, llvm::StringRef modpath);
 139 static llvm::SmallVector<llvm::GlobalValueSummary *, 1>
 140 summaries_for_guid(const InlineSearchPath& path, llvm::GlobalValue::GUID guid);
 141
 142 /* verbose debugging for inliner development */
 143 /* #define INLINE_DEBUG */
 144 #ifdef INLINE_DEBUG
 145 #define ilog            elog
 146 #else
 147 #define ilog(...)       (void) 0
 148 #endif
 149
 150 /*
 151  * Reset inlining related state. This needs to be called before the currently
 152  * used LLVMContextRef is disposed (and a new one create), otherwise we would
 153  * have dangling references to deleted modules.
 154  */
 155 void
 156 llvm_inline_reset_caches(void)
 157 {
 158         module_cache->clear();
 159         summary_cache->clear();
 160 }
 161
 162 /*
 163  * Perform inlining of external function references in M based on a simple
 164  * cost based analysis.
 165  */
 166 void
 167 llvm_inline(LLVMModuleRef M)
 168 {
 169         LLVMContextRef lc = LLVMGetModuleContext(M);
 170         llvm::Module *mod = llvm::unwrap(M);
 171
 172         std::unique_ptr<ImportMapTy> globalsToInline = llvm_build_inline_plan(lc, mod);
 173         if (!globalsToInline)
 174                 return;
 175         llvm_execute_inline_plan(mod, globalsToInline.get());
 176 }
 177
 178 /*
 179  * Build information necessary for inlining external function references in
 180  * mod.
 181  */
 182 static std::unique_ptr<ImportMapTy>
 183 llvm_build_inline_plan(LLVMContextRef lc, llvm::Module *mod)
 184 {
 185         std::unique_ptr<ImportMapTy> globalsToInline(new ImportMapTy());
 186         FunctionInlineStates functionStates;
 187         InlineWorkList worklist;
 188
 189         InlineSearchPath defaultSearchPath;
 190
 191         /* attempt to add module to search path */
 192         add_module_to_inline_search_path(defaultSearchPath, "$libdir/postgres");
 193         /* if postgres isn't available, no point continuing */
 194         if (defaultSearchPath.empty())
 195                 return nullptr;
 196
 197         /*
 198          * Start inlining with current references to external functions by putting
 199          * them on the inlining worklist. If, during inlining of those, new extern
 200          * functions need to be inlined, they'll also be put there, with a lower
 201          * priority.
 202          */
 203         for (const llvm::Function &funcDecl : mod->functions())
 204         {
 205                 InlineWorkListItem item = {};
 206                 FunctionInlineState inlineState = {};
 207
 208                 /* already has a definition */
 209                 if (!funcDecl.isDeclaration())
 210                         continue;
 211
 212                 /* llvm provides implementation */
 213                 if (funcDecl.isIntrinsic())
 214                         continue;
 215
 216                 item.symbolName = funcDecl.getName();
 217                 item.searchpath = defaultSearchPath;
 218                 worklist.push_back(item);
 219                 inlineState.costLimit = inline_initial_cost;
 220                 inlineState.processed = false;
 221                 inlineState.inlined = false;
 222                 inlineState.allowReconsidering = false;
 223                 functionStates[funcDecl.getName()] = inlineState;
 224         }
 225
 226         /*
 227          * Iterate over pending worklist items, look them up in index, check
 228          * whether they should be inlined.
 229          */
 230         while (!worklist.empty())
 231         {
 232                 InlineWorkListItem item = worklist.pop_back_val();
 233                 llvm::StringRef symbolName = item.symbolName;
 234                 char *cmodname;
 235                 char *cfuncname;
 236                 FunctionInlineState &inlineState = functionStates[symbolName];
 237                 llvm::GlobalValue::GUID funcGUID;
 238
 239                 llvm_split_symbol_name(symbolName.data(), &cmodname, &cfuncname);
 240
 241                 funcGUID = llvm::GlobalValue::getGUID(cfuncname);
 242
 243                 /* already processed */
 244                 if (inlineState.processed)
 245                         continue;
 246
 247
 248                 if (cmodname)
 249                         add_module_to_inline_search_path(item.searchpath, cmodname);
 250
 251                 /*
 252                  * Iterate over all known definitions of function, via the index. Then
 253                  * look up module(s), check if function actually is defined (there
 254                  * could be hash conflicts).
 255                  */
 256                 for (const auto &gvs : summaries_for_guid(item.searchpath, funcGUID))
 257                 {
 258                         const llvm::FunctionSummary *fs;
 259                         llvm::StringRef modPath = gvs->modulePath();
 260                         llvm::Module *defMod;
 261                         llvm::Function *funcDef;
 262
 263                         fs = llvm::cast<llvm::FunctionSummary>(gvs);
 264
 265                         if (gvs->notEligibleToImport())
 266                         {
 267                                 ilog(DEBUG1, "ineligibile to import %s due to summary",
 268                                          symbolName.data());
 269                                 continue;
 270                         }
 271
 272                         if ((int) fs->instCount() > inlineState.costLimit)
 273                         {
 274                                 ilog(DEBUG1, "ineligibile to import %s due to early threshold: %u vs %u",
 275                                          symbolName.data(), fs->instCount(), inlineState.costLimit);
 276                                 inlineState.allowReconsidering = true;
 277                                 continue;
 278                         }
 279
 280                         defMod = load_module_cached(lc, modPath);
 281                         if (defMod->materializeMetadata())
 282                                 elog(FATAL, "failed to materialize metadata");
 283
 284                         funcDef = defMod->getFunction(cfuncname);
 285
 286                         /*
 287                          * This can happen e.g. in case of a hash collision of the
 288                          * function's name.
 289                          */
 290                         if (!funcDef)
 291                                 continue;
 292
 293                         if (funcDef->materialize())
 294                                 elog(FATAL, "failed to materialize metadata");
 295
 296                         Assert(!funcDef->isDeclaration());
 297                         Assert(funcDef->hasExternalLinkage());
 298
 299                         llvm::StringSet<> importVars;
 300                         llvm::SmallPtrSet<const llvm::Function *, 8> visitedFunctions;
 301                         int running_instcount = 0;
 302
 303                         /*
 304                          * Check whether function, and objects it depends on, are
 305                          * inlinable.
 306                          */
 307                         if (function_inlinable(*funcDef,
 308                                                                    inlineState.costLimit,
 309                                                                    functionStates,
 310                                                                    worklist,
 311                                                                    item.searchpath,
 312                                                                    visitedFunctions,
 313                                                                    running_instcount,
 314                                                                    importVars))
 315                         {
 316                                 /*
 317                                  * Check whether function and all its dependencies are too
 318                                  * big. Dependencies already counted for other functions that
 319                                  * will get inlined are not counted again. While this make
 320                                  * things somewhat order dependent, I can't quite see a point
 321                                  * in a different behaviour.
 322                                  */
 323                                 if (running_instcount > inlineState.costLimit)
 324                                 {
 325                                         ilog(DEBUG1, "skipping inlining of %s due to late threshold %d vs %d",
 326                                                  symbolName.data(), running_instcount, inlineState.costLimit);
 327                                         inlineState.allowReconsidering = true;
 328                                         continue;
 329                                 }
 330
 331                                 ilog(DEBUG1, "inline top function %s total_instcount: %d, partial: %d",
 332                                          symbolName.data(), running_instcount, fs->instCount());
 333
 334                                 /* import referenced function itself */
 335                                 importVars.insert(symbolName);
 336
 337                                 {
 338                                         llvm::StringSet<> &modGlobalsToInline = (*globalsToInline)[modPath];
 339                                         for (auto& importVar : importVars)
 340                                                 modGlobalsToInline.insert(importVar.first());
 341                                         Assert(modGlobalsToInline.size() > 0);
 342                                 }
 343
 344                                 /* mark function as inlined */
 345                                 inlineState.inlined = true;
 346
 347                                 /*
 348                                  * Found definition to inline, don't look for further
 349                                  * potential definitions.
 350                                  */
 351                                 break;
 352                         }
 353                         else
 354                         {
 355                                 ilog(DEBUG1, "had to skip inlining %s",
 356                                          symbolName.data());
 357
 358                                 /* It's possible there's another definition that's inlinable. */
 359                         }
 360                 }
 361
 362                 /*
 363                  * Signal that we're done with symbol, whether successful (inlined =
 364                  * true above) or not.
 365                  */
 366                 inlineState.processed = true;
 367         }
 368
 369         return globalsToInline;
 370 }
 371
 372 /*
 373  * Perform the actual inlining of external functions (and their dependencies)
 374  * into mod.
 375  */
 376 static void
 377 llvm_execute_inline_plan(llvm::Module *mod, ImportMapTy *globalsToInline)
 378 {
 379         llvm::IRMover Mover(*mod);
 380
 381         for (const auto& toInline : *globalsToInline)
 382         {
 383                 const llvm::StringRef& modPath = toInline.first();
 384                 const llvm::StringSet<>& modGlobalsToInline = toInline.second;
 385                 llvm::SetVector<llvm::GlobalValue *> GlobalsToImport;
 386
 387                 Assert(module_cache->count(modPath));
 388                 std::unique_ptr<llvm::Module> importMod(std::move((*module_cache)[modPath]));
 389                 module_cache->erase(modPath);
 390
 391                 if (modGlobalsToInline.empty())
 392                         continue;
 393
 394                 for (auto &glob: modGlobalsToInline)
 395                 {
 396                         llvm::StringRef SymbolName = glob.first();
 397                         char *modname;
 398                         char *funcname;
 399
 400                         llvm_split_symbol_name(SymbolName.data(), &modname, &funcname);
 401
 402                         llvm::GlobalValue *valueToImport = importMod->getNamedValue(funcname);
 403
 404                         if (!valueToImport)
 405                                 elog(FATAL, "didn't refind value %s to import", SymbolName.data());
 406
 407                         /*
 408                          * For functions (global vars are only inlined if already static),
 409                          * mark imported variables as being clones from other
 410                          * functions. That a) avoids symbol conflicts b) allows the
 411                          * optimizer to perform inlining.
 412                         */
 413                         if (llvm::isa<llvm::Function>(valueToImport))
 414                         {
 415                                 llvm::Function *F = llvm::dyn_cast<llvm::Function>(valueToImport);
 416                                 typedef llvm::GlobalValue::LinkageTypes LinkageTypes;
 417
 418                                 /*
 419                                  * Per-function info isn't necessarily stripped yet, as the
 420                                  * module is lazy-loaded when stripped above.
 421                                  */
 422                                 llvm::stripDebugInfo(*F);
 423
 424                                 /*
 425                                  * If the to-be-imported function is one referenced including
 426                                  * its module name, create a tiny inline function that just
 427                                  * forwards the call. One might think a GlobalAlias would do
 428                                  * the trick, but a) IRMover doesn't override a declaration
 429                                  * with an alias pointing to a definition (instead renaming
 430                                  * it), b) Aliases can't be AvailableExternally.
 431                                  */
 432                                 if (modname)
 433                                 {
 434                                         llvm::Function *AF;
 435
 436                                         AF = create_redirection_function(importMod, F, SymbolName);
 437
 438                                         GlobalsToImport.insert(AF);
 439                                         llvm::stripDebugInfo(*AF);
 440                                 }
 441
 442                                 if (valueToImport->hasExternalLinkage())
 443                                 {
 444                                         valueToImport->setLinkage(LinkageTypes::AvailableExternallyLinkage);
 445                                 }
 446                         }
 447
 448                         GlobalsToImport.insert(valueToImport);
 449                         ilog(DEBUG1, "performing import of %s %s",
 450                                  modPath.data(), SymbolName.data());
 451
 452                 }
 453
 454                 if (Mover.move(std::move(importMod), GlobalsToImport.getArrayRef(),
 455                                            [](llvm::GlobalValue &, llvm::IRMover::ValueAdder) {},
 456                                            /*IsPerformingImport=*/false))
 457                         elog(FATAL, "function import failed with linker error");
 458         }
 459 }
 460
 461 /*
 462  * Return a module identified by modPath, caching it in memory.
 463  *
 464  * Note that such a module may *not* be modified without copying, otherwise
 465  * the cache state would get corrupted.
 466  */
 467 static llvm::Module*
 468 load_module_cached(LLVMContextRef lc, llvm::StringRef modPath)
 469 {
 470         auto it = module_cache->find(modPath);
 471         if (it == module_cache->end())
 472         {
 473                 it = module_cache->insert(
 474                         std::make_pair(modPath, load_module(lc, modPath))).first;
 475         }
 476
 477         return it->second.get();
 478 }
 479
 480 static std::unique_ptr<llvm::Module>
 481 load_module(LLVMContextRef lc, llvm::StringRef Identifier)
 482 {
 483         LLVMMemoryBufferRef buf;
 484         LLVMModuleRef mod;
 485         char path[MAXPGPATH];
 486         char *msg;
 487
 488         snprintf(path, MAXPGPATH,"%s/bitcode/%s", pkglib_path, Identifier.data());
 489
 490         if (LLVMCreateMemoryBufferWithContentsOfFile(path, &buf, &msg))
 491                 elog(FATAL, "failed to open bitcode file \"%s\": %s",
 492                          path, msg);
 493         if (LLVMGetBitcodeModuleInContext2(lc, buf, &mod))
 494                 elog(FATAL, "failed to parse bitcode in file \"%s\"", path);
 495
 496         /*
 497          * Currently there's no use in more detailed debug info for JITed
 498          * code. Until that changes, not much point in wasting memory and cycles
 499          * on processing debuginfo.
 500          */
 501         llvm::StripDebugInfo(*llvm::unwrap(mod));
 502
 503         return std::unique_ptr<llvm::Module>(llvm::unwrap(mod));
 504 }
 505
 506 /*
 507  * Compute list of referenced variables, functions and the instruction count
 508  * for a function.
 509  */
 510 static void
 511 function_references(llvm::Function &F,
 512                                         int &running_instcount,
 513                                         llvm::SmallPtrSet<llvm::GlobalVariable *, 8> &referencedVars,
 514                                         llvm::SmallPtrSet<llvm::Function *, 8> &referencedFunctions)
 515 {
 516         llvm::SmallPtrSet<const llvm::User *, 32> Visited;
 517
 518         for (llvm::BasicBlock &BB : F)
 519         {
 520                 for (llvm::Instruction &I : BB)
 521                 {
 522                         if (llvm::isa<llvm::DbgInfoIntrinsic>(I))
 523                                 continue;
 524
 525                         llvm::SmallVector<llvm::User *, 8> Worklist;
 526                         Worklist.push_back(&I);
 527
 528                         running_instcount++;
 529
 530                         while (!Worklist.empty()) {
 531                                 llvm::User *U = Worklist.pop_back_val();
 532
 533                                 /* visited before */
 534                                 if (!Visited.insert(U).second)
 535                                         continue;
 536
 537                                 for (auto &OI : U->operands()) {
 538                                         llvm::User *Operand = llvm::dyn_cast<llvm::User>(OI);
 539                                         if (!Operand)
 540                                                 continue;
 541                                         if (llvm::isa<llvm::BlockAddress>(Operand))
 542                                                 continue;
 543                                         if (auto *GV = llvm::dyn_cast<llvm::GlobalVariable>(Operand)) {
 544                                                 referencedVars.insert(GV);
 545                                                 if (GV->hasInitializer())
 546                                                         Worklist.push_back(GV->getInitializer());
 547                                                 continue;
 548                                         }
 549                                         if (auto *CF = llvm::dyn_cast<llvm::Function>(Operand)) {
 550                                                 referencedFunctions.insert(CF);
 551                                                 continue;
 552                                         }
 553                                         Worklist.push_back(Operand);
 554                                 }
 555                         }
 556                 }
 557         }
 558 }
 559
 560 /*
 561  * Check whether function F is inlinable and, if so, what globals need to be
 562  * imported.
 563  *
 564  * References to external functions from, potentially recursively, inlined
 565  * functions are added to the passed in worklist.
 566  */
 567 static bool
 568 function_inlinable(llvm::Function &F,
 569                                    int threshold,
 570                                    FunctionInlineStates &functionStates,
 571                                    InlineWorkList &worklist,
 572                                    InlineSearchPath &searchpath,
 573                                    llvm::SmallPtrSet<const llvm::Function *, 8> &visitedFunctions,
 574                                    int &running_instcount,
 575                                    llvm::StringSet<> &importVars)
 576 {
 577         int subThreshold = threshold * inline_cost_decay_factor;
 578         llvm::SmallPtrSet<llvm::GlobalVariable *, 8> referencedVars;
 579         llvm::SmallPtrSet<llvm::Function *, 8> referencedFunctions;
 580
 581         /* can't rely on what may be inlined */
 582         if (F.isInterposable())
 583                 return false;
 584
 585         /*
 586          * Can't rely on function being present. Alternatively we could create a
 587          * static version of these functions?
 588          */
 589         if (F.hasAvailableExternallyLinkage())
 590                 return false;
 591
 592         ilog(DEBUG1, "checking inlinability of %s", F.getName().data());
 593
 594         if (F.materialize())
 595                 elog(FATAL, "failed to materialize metadata");
 596
 597         if (F.getAttributes().hasFnAttr(llvm::Attribute::NoInline))
 598         {
 599                 ilog(DEBUG1, "ineligibile to import %s due to noinline",
 600                          F.getName().data());
 601                 return false;
 602         }
 603
 604         function_references(F, running_instcount, referencedVars, referencedFunctions);
 605
 606         for (llvm::GlobalVariable* rv: referencedVars)
 607         {
 608                 if (rv->materialize())
 609                         elog(FATAL, "failed to materialize metadata");
 610
 611                 /*
 612                  * Don't inline functions that access thread local variables.  That
 613                  * doesn't work on current LLVM releases (but might in future).
 614                  */
 615                 if (rv->isThreadLocal())
 616                 {
 617                         ilog(DEBUG1, "cannot inline %s due to thread-local variable %s",
 618                                  F.getName().data(), rv->getName().data());
 619                         return false;
 620                 }
 621
 622                 /*
 623                  * Never want to inline externally visible vars, cheap enough to
 624                  * reference.
 625                  */
 626                 if (rv->hasExternalLinkage() || rv->hasAvailableExternallyLinkage())
 627                         continue;
 628
 629                 /*
 630                  * If variable is file-local, we need to inline it, to be able to
 631                  * inline the function itself. Can't do that if the variable can be
 632                  * modified, because they'd obviously get out of sync.
 633                  *
 634                  * XXX: Currently not a problem, but there'd be problems with
 635                  * nontrivial initializers if they were allowed for postgres.
 636                  */
 637                 if (!rv->isConstant())
 638                 {
 639                         ilog(DEBUG1, "cannot inline %s due to uncloneable variable %s",
 640                                  F.getName().data(), rv->getName().data());
 641                         return false;
 642                 }
 643
 644                 ilog(DEBUG1, "memorizing global var %s linkage %d for inlining",
 645                          rv->getName().data(), (int)rv->getLinkage());
 646
 647                 importVars.insert(rv->getName());
 648                 /* small cost attributed to each cloned global */
 649                 running_instcount += 5;
 650         }
 651
 652         visitedFunctions.insert(&F);
 653
 654         /*
 655          * Check referenced functions. Check whether used static ones are
 656          * inlinable, and remember external ones for inlining.
 657          */
 658         for (llvm::Function* referencedFunction: referencedFunctions)
 659         {
 660                 llvm::StringSet<> recImportVars;
 661
 662                 if (referencedFunction->materialize())
 663                         elog(FATAL, "failed to materialize metadata");
 664
 665                 if (referencedFunction->isIntrinsic())
 666                         continue;
 667
 668                 /* if already visited skip, otherwise remember */
 669                 if (!visitedFunctions.insert(referencedFunction).second)
 670                         continue;
 671
 672                 /*
 673                  * We don't inline external functions directly here, instead we put
 674                  * them on the worklist if appropriate and check them from
 675                  * llvm_build_inline_plan().
 676                  */
 677                 if (referencedFunction->hasExternalLinkage())
 678                 {
 679                         llvm::StringRef funcName = referencedFunction->getName();
 680
 681                         /*
 682                          * Don't bother checking for inlining if remaining cost budget is
 683                          * very small.
 684                          */
 685                         if (subThreshold < 5)
 686                                 continue;
 687
 688                         auto it = functionStates.find(funcName);
 689                         if (it == functionStates.end())
 690                         {
 691                                 FunctionInlineState inlineState;
 692
 693                                 inlineState.costLimit = subThreshold;
 694                                 inlineState.processed = false;
 695                                 inlineState.inlined = false;
 696                                 inlineState.allowReconsidering = false;
 697
 698                                 functionStates[funcName] = inlineState;
 699                                 worklist.push_back({funcName, searchpath});
 700
 701                                 ilog(DEBUG1,
 702                                          "considering extern function %s at %d for inlining",
 703                                          funcName.data(), subThreshold);
 704                         }
 705                         else if (!it->second.inlined &&
 706                                          (!it->second.processed || it->second.allowReconsidering) &&
 707                                          it->second.costLimit < subThreshold)
 708                         {
 709                                 /*
 710                                  * Update inlining threshold if higher. Need to re-queue
 711                                  * to be processed if already processed with lower
 712                                  * threshold.
 713                                  */
 714                                 if (it->second.processed)
 715                                 {
 716                                         ilog(DEBUG1,
 717                                                  "reconsidering extern function %s at %d for inlining, increasing from %d",
 718                                                  funcName.data(), subThreshold, it->second.costLimit);
 719
 720                                         it->second.processed = false;
 721                                         it->second.allowReconsidering = false;
 722                                         worklist.push_back({funcName, searchpath});
 723                                 }
 724                                 it->second.costLimit = subThreshold;
 725                         }
 726                         continue;
 727                 }
 728
 729                 /* can't rely on what may be inlined */
 730                 if (referencedFunction->isInterposable())
 731                         return false;
 732
 733                 if (!function_inlinable(*referencedFunction,
 734                                                                 subThreshold,
 735                                                                 functionStates,
 736                                                                 worklist,
 737                                                                 searchpath,
 738                                                                 visitedFunctions,
 739                                                                 running_instcount,
 740                                                                 recImportVars))
 741                 {
 742                         ilog(DEBUG1,
 743                                  "cannot inline %s due to required function %s not being inlinable",
 744                                  F.getName().data(), referencedFunction->getName().data());
 745                         return false;
 746                 }
 747
 748                 /* import referenced function itself */
 749                 importVars.insert(referencedFunction->getName());
 750
 751                 /* import referenced function and its dependents */
 752                 for (auto& recImportVar : recImportVars)
 753                         importVars.insert(recImportVar.first());
 754         }
 755
 756         return true;
 757 }
 758
 759 /*
 760  * Attempt to load module summary located at path. Return empty pointer when
 761  * loading fails.
 762  */
 763 static std::unique_ptr<llvm::ModuleSummaryIndex>
 764 llvm_load_summary(llvm::StringRef path)
 765 {
 766         llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer> > MBOrErr =
 767                 llvm::MemoryBuffer::getFile(path);
 768
 769         if (std::error_code EC = MBOrErr.getError())
 770         {
 771                 ilog(DEBUG1, "failed to open %s: %s", path.data(),
 772                          EC.message().c_str());
 773         }
 774         else
 775         {
 776                 llvm::MemoryBufferRef ref(*MBOrErr.get().get());
 777
 778                 llvm::Expected<std::unique_ptr<llvm::ModuleSummaryIndex> > IndexOrErr =
 779                         llvm::getModuleSummaryIndex(ref);
 780                 if (IndexOrErr)
 781                         return std::move(IndexOrErr.get());
 782                 elog(FATAL, "failed to load summary \"%s\": %s",
 783                          path.data(),
 784                          toString(IndexOrErr.takeError()).c_str());
 785         }
 786         return nullptr;
 787 }
 788
 789 /*
 790  * Attempt to add modpath to the search path.
 791  */
 792 static void
 793 add_module_to_inline_search_path(InlineSearchPath& searchpath, llvm::StringRef modpath)
 794 {
 795         /* only extension in libdir are candidates for inlining for now */
 796 #if LLVM_VERSION_MAJOR < 16
 797 #define starts_with startswith
 798 #endif
 799         if (!modpath.starts_with("$libdir/"))
 800                 return;
 801
 802         /* if there's no match, attempt to load */
 803         auto it = summary_cache->find(modpath);
 804         if (it == summary_cache->end())
 805         {
 806                 std::string path(modpath);
 807                 path = path.replace(0, strlen("$libdir"), std::string(pkglib_path) + "/bitcode");
 808                 path += ".index.bc";
 809                 (*summary_cache)[modpath] = llvm_load_summary(path);
 810                 it = summary_cache->find(modpath);
 811         }
 812
 813         Assert(it != summary_cache->end());
 814
 815         /* if the entry isn't NULL, it's validly loaded */
 816         if (it->second)
 817                 searchpath.push_back(it->second.get());
 818 }
 819
 820 /*
 821  * Search for all references for functions hashing to guid in the search path,
 822  * and return them in search path order.
 823  */
 824 static llvm::SmallVector<llvm::GlobalValueSummary *, 1>
 825 summaries_for_guid(const InlineSearchPath& path, llvm::GlobalValue::GUID guid)
 826 {
 827         llvm::SmallVector<llvm::GlobalValueSummary *, 1> matches;
 828
 829         for (auto index : path)
 830         {
 831                 llvm::ValueInfo funcVI = index->getValueInfo(guid);
 832
 833                 /* if index doesn't know function, we don't have a body, continue */
 834                 if (funcVI)
 835                         for (auto &gv : funcVI.getSummaryList())
 836                                 matches.push_back(gv.get());
 837         }
 838
 839         return matches;
 840 }
 841
 842 /*
 843  * Create inline wrapper with the name Name, redirecting the call to F.
 844  */
 845 static llvm::Function*
 846 create_redirection_function(std::unique_ptr<llvm::Module> &importMod,
 847                                                         llvm::Function *F,
 848                                                         llvm::StringRef Name)
 849 {
 850         typedef llvm::GlobalValue::LinkageTypes LinkageTypes;
 851
 852         llvm::LLVMContext &Context = F->getContext();
 853         llvm::IRBuilder<> Builder(Context);
 854         llvm::Function *AF;
 855         llvm::BasicBlock *BB;
 856         llvm::CallInst *fwdcall;
 857
 858         AF = llvm::Function::Create(F->getFunctionType(),
 859                                                                 LinkageTypes::AvailableExternallyLinkage,
 860                                                                 Name, importMod.get());
 861         BB = llvm::BasicBlock::Create(Context, "entry", AF);
 862
 863         Builder.SetInsertPoint(BB);
 864         fwdcall = Builder.CreateCall(F, &*AF->arg_begin());
 865         fwdcall->addFnAttr(llvm::Attribute::AlwaysInline);
 866         Builder.CreateRet(fwdcall);
 867
 868         return AF;
 869 }