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 imorted.
13  *
14  * Copyright (c) 2016-2018, 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 #if LLVM_VERSION_MAJOR > 3
53 #include <llvm/Bitcode/BitcodeReader.h>
54 #else
55 #include <llvm/Bitcode/ReaderWriter.h>
56 #include <llvm/Support/Error.h>
57 #endif
58 #include <llvm/IR/Attributes.h>
59 #include <llvm/IR/DebugInfo.h>
60 #include <llvm/IR/IntrinsicInst.h>
61 #include <llvm/IR/IRBuilder.h>
62 #include <llvm/IR/ModuleSummaryIndex.h>
63 #include <llvm/Linker/IRMover.h>
64 #include <llvm/Support/ManagedStatic.h>
65 
66 
67 /*
68  * Type used to represent modules InlineWorkListItem's subject is searched for
69  * in.
70  */
71 typedef llvm::SmallVector<llvm::ModuleSummaryIndex *, 2> InlineSearchPath;
72 
73 /*
74  * Item in queue of to-be-checked symbols and corresponding queue.
75  */
76 typedef struct InlineWorkListItem
77 {
78 	llvm::StringRef symbolName;
79 	llvm::SmallVector<llvm::ModuleSummaryIndex *, 2> searchpath;
80 } InlineWorkListItem;
81 typedef llvm::SmallVector<InlineWorkListItem, 128> InlineWorkList;
82 
83 /*
84  * Information about symbols processed during inlining. Used to prevent
85  * repeated searches and provide additional information.
86  */
87 typedef struct FunctionInlineState
88 {
89 	int costLimit;
90 	bool processed;
91 	bool inlined;
92 	bool allowReconsidering;
93 } FunctionInlineState;
94 typedef llvm::StringMap<FunctionInlineState> FunctionInlineStates;
95 
96 /*
97  * Map of modules that should be inlined, with a list of the to-be inlined
98  * symbols.
99  */
100 typedef llvm::StringMap<llvm::StringSet<> > ImportMapTy;
101 
102 
103 const float inline_cost_decay_factor = 0.5;
104 const int inline_initial_cost = 150;
105 
106 /*
107  * These are managed statics so LLVM knows to deallocate them during an
108  * LLVMShutdown(), rather than after (which'd cause crashes).
109  */
110 typedef llvm::StringMap<std::unique_ptr<llvm::Module> > ModuleCache;
111 llvm::ManagedStatic<ModuleCache> module_cache;
112 typedef llvm::StringMap<std::unique_ptr<llvm::ModuleSummaryIndex> > SummaryCache;
113 llvm::ManagedStatic<SummaryCache> summary_cache;
114 
115 
116 static std::unique_ptr<ImportMapTy> llvm_build_inline_plan(llvm::Module *mod);
117 static void llvm_execute_inline_plan(llvm::Module *mod,
118 									 ImportMapTy *globalsToInline);
119 
120 static llvm::Module* load_module_cached(llvm::StringRef modPath);
121 static std::unique_ptr<llvm::Module> load_module(llvm::StringRef Identifier);
122 static std::unique_ptr<llvm::ModuleSummaryIndex> llvm_load_summary(llvm::StringRef path);
123 
124 
125 static llvm::Function* create_redirection_function(std::unique_ptr<llvm::Module> &importMod,
126 												   llvm::Function *F,
127 												   llvm::StringRef Name);
128 
129 static bool function_inlinable(llvm::Function &F,
130 							   int threshold,
131 							   FunctionInlineStates &functionState,
132 							   InlineWorkList &worklist,
133 							   InlineSearchPath &searchpath,
134 							   llvm::SmallPtrSet<const llvm::Function *, 8> &visitedFunctions,
135 							   int &running_instcount,
136 							   llvm::StringSet<> &importVars);
137 static void function_references(llvm::Function &F,
138 								int &running_instcount,
139 								llvm::SmallPtrSet<llvm::GlobalVariable *, 8> &referencedVars,
140 								llvm::SmallPtrSet<llvm::Function *, 8> &referencedFunctions);
141 
142 static void add_module_to_inline_search_path(InlineSearchPath& path, llvm::StringRef modpath);
143 static llvm::SmallVector<llvm::GlobalValueSummary *, 1>
144 summaries_for_guid(const InlineSearchPath& path, llvm::GlobalValue::GUID guid);
145 
146 /* verbose debugging for inliner development */
147 /* #define INLINE_DEBUG */
148 #ifdef INLINE_DEBUG
149 #define ilog		elog
150 #else
151 #define ilog(...)	(void) 0
152 #endif
153 
154 /*
155  * Perform inlining of external function references in M based on a simple
156  * cost based analysis.
157  */
158 void
llvm_inline(LLVMModuleRef M)159 llvm_inline(LLVMModuleRef M)
160 {
161 	llvm::Module *mod = llvm::unwrap(M);
162 
163 	std::unique_ptr<ImportMapTy> globalsToInline = llvm_build_inline_plan(mod);
164 	if (!globalsToInline)
165 		return;
166 	llvm_execute_inline_plan(mod, globalsToInline.get());
167 }
168 
169 /*
170  * Build information necessary for inlining external function references in
171  * mod.
172  */
173 static std::unique_ptr<ImportMapTy>
llvm_build_inline_plan(llvm::Module * mod)174 llvm_build_inline_plan(llvm::Module *mod)
175 {
176 	std::unique_ptr<ImportMapTy> globalsToInline(new ImportMapTy());
177 	FunctionInlineStates functionStates;
178 	InlineWorkList worklist;
179 
180 	InlineSearchPath defaultSearchPath;
181 
182 	/* attempt to add module to search path */
183 	add_module_to_inline_search_path(defaultSearchPath, "$libdir/postgres");
184 	/* if postgres isn't available, no point continuing */
185 	if (defaultSearchPath.empty())
186 		return nullptr;
187 
188 	/*
189 	 * Start inlining with current references to external functions by putting
190 	 * them on the inlining worklist. If, during inlining of those, new extern
191 	 * functions need to be inlined, they'll also be put there, with a lower
192 	 * priority.
193 	 */
194 	for (const llvm::Function &funcDecl : mod->functions())
195 	{
196 		InlineWorkListItem item = {};
197 		FunctionInlineState inlineState = {};
198 
199 		/* already has a definition */
200 		if (!funcDecl.isDeclaration())
201 			continue;
202 
203 		/* llvm provides implementation */
204 		if (funcDecl.isIntrinsic())
205 			continue;
206 
207 		item.symbolName = funcDecl.getName();
208 		item.searchpath = defaultSearchPath;
209 		worklist.push_back(item);
210 		inlineState.costLimit = inline_initial_cost;
211 		inlineState.processed = false;
212 		inlineState.inlined = false;
213 		inlineState.allowReconsidering = false;
214 		functionStates[funcDecl.getName()] = inlineState;
215 	}
216 
217 	/*
218 	 * Iterate over pending worklist items, look them up in index, check
219 	 * whether they should be inlined.
220 	 */
221 	while (!worklist.empty())
222 	{
223 		InlineWorkListItem item = worklist.pop_back_val();
224 		llvm::StringRef symbolName = item.symbolName;
225 		char *cmodname;
226 		char *cfuncname;
227 		FunctionInlineState &inlineState = functionStates[symbolName];
228 		llvm::GlobalValue::GUID funcGUID;
229 
230 		llvm_split_symbol_name(symbolName.data(), &cmodname, &cfuncname);
231 
232 		funcGUID = llvm::GlobalValue::getGUID(cfuncname);
233 
234 		/* already processed */
235 		if (inlineState.processed)
236 			continue;
237 
238 
239 		if (cmodname)
240 			add_module_to_inline_search_path(item.searchpath, cmodname);
241 
242 		/*
243 		 * Iterate over all known definitions of function, via the index. Then
244 		 * look up module(s), check if function actually is defined (there
245 		 * could be hash conflicts).
246 		 */
247 		for (const auto &gvs : summaries_for_guid(item.searchpath, funcGUID))
248 		{
249 			const llvm::FunctionSummary *fs;
250 			llvm::StringRef modPath = gvs->modulePath();
251 			llvm::Module *defMod;
252 			llvm::Function *funcDef;
253 
254 			fs = llvm::cast<llvm::FunctionSummary>(gvs);
255 
256 #if LLVM_VERSION_MAJOR > 3
257 			if (gvs->notEligibleToImport())
258 			{
259 				ilog(DEBUG1, "ineligibile to import %s due to summary",
260 					 symbolName.data());
261 				continue;
262 			}
263 #endif
264 
265 			if ((int) fs->instCount() > inlineState.costLimit)
266 			{
267 				ilog(DEBUG1, "ineligibile to import %s due to early threshold: %u vs %u",
268 					 symbolName.data(), fs->instCount(), inlineState.costLimit);
269 				inlineState.allowReconsidering = true;
270 				continue;
271 			}
272 
273 			defMod = load_module_cached(modPath);
274 			if (defMod->materializeMetadata())
275 				elog(FATAL, "failed to materialize metadata");
276 
277 			funcDef = defMod->getFunction(cfuncname);
278 
279 			/*
280 			 * This can happen e.g. in case of a hash collision of the
281 			 * function's name.
282 			 */
283 			if (!funcDef)
284 				continue;
285 
286 			if (funcDef->materialize())
287 				elog(FATAL, "failed to materialize metadata");
288 
289 			Assert(!funcDef->isDeclaration());
290 			Assert(funcDef->hasExternalLinkage());
291 
292 			llvm::StringSet<> importVars;
293 			llvm::SmallPtrSet<const llvm::Function *, 8> visitedFunctions;
294 			int running_instcount = 0;
295 
296 			/*
297 			 * Check whether function, and objects it depends on, are
298 			 * inlinable.
299 			 */
300 			if (function_inlinable(*funcDef,
301 								   inlineState.costLimit,
302 								   functionStates,
303 								   worklist,
304 								   item.searchpath,
305 								   visitedFunctions,
306 								   running_instcount,
307 								   importVars))
308 			{
309 				/*
310 				 * Check whether function and all its dependencies are too
311 				 * big. Dependencies already counted for other functions that
312 				 * will get inlined are not counted again. While this make
313 				 * things somewhat order dependant, I can't quite see a point
314 				 * in a different behaviour.
315 				 */
316 				if (running_instcount > inlineState.costLimit)
317 				{
318 					ilog(DEBUG1, "skipping inlining of %s due to late threshold %d vs %d",
319 						 symbolName.data(), running_instcount, inlineState.costLimit);
320 					inlineState.allowReconsidering = true;
321 					continue;
322 				}
323 
324 				ilog(DEBUG1, "inline top function %s total_instcount: %d, partial: %d",
325 					 symbolName.data(), running_instcount, fs->instCount());
326 
327 				/* import referenced function itself */
328 				importVars.insert(symbolName);
329 
330 				{
331 					llvm::StringSet<> &modGlobalsToInline = (*globalsToInline)[modPath];
332 					for (auto& importVar : importVars)
333 						modGlobalsToInline.insert(importVar.first());
334 					Assert(modGlobalsToInline.size() > 0);
335 				}
336 
337 				/* mark function as inlined */
338 				inlineState.inlined = true;
339 
340 				/*
341 				 * Found definition to inline, don't look for further
342 				 * potential definitions.
343 				 */
344 				break;
345 			}
346 			else
347 			{
348 				ilog(DEBUG1, "had to skip inlining %s",
349 					 symbolName.data());
350 
351 				/* It's possible there's another definition that's inlinable. */
352 			}
353 		}
354 
355 		/*
356 		 * Signal that we're done with symbol, whether successful (inlined =
357 		 * true above) or not.
358 		 */
359 		inlineState.processed = true;
360 	}
361 
362 	return globalsToInline;
363 }
364 
365 /*
366  * Perform the actual inlining of external functions (and their dependencies)
367  * into mod.
368  */
369 static void
llvm_execute_inline_plan(llvm::Module * mod,ImportMapTy * globalsToInline)370 llvm_execute_inline_plan(llvm::Module *mod, ImportMapTy *globalsToInline)
371 {
372 	llvm::IRMover Mover(*mod);
373 
374 	for (const auto& toInline : *globalsToInline)
375 	{
376 		const llvm::StringRef& modPath = toInline.first();
377 		const llvm::StringSet<>& modGlobalsToInline = toInline.second;
378 		llvm::SetVector<llvm::GlobalValue *> GlobalsToImport;
379 
380 		Assert(module_cache->count(modPath));
381 		std::unique_ptr<llvm::Module> importMod(std::move((*module_cache)[modPath]));
382 		module_cache->erase(modPath);
383 
384 		if (modGlobalsToInline.empty())
385 			continue;
386 
387 		for (auto &glob: modGlobalsToInline)
388 		{
389 			llvm::StringRef SymbolName = glob.first();
390 			char *modname;
391 			char *funcname;
392 
393 			llvm_split_symbol_name(SymbolName.data(), &modname, &funcname);
394 
395 			llvm::GlobalValue *valueToImport = importMod->getNamedValue(funcname);
396 
397 			if (!valueToImport)
398 				elog(FATAL, "didn't refind value %s to import", SymbolName.data());
399 
400 			/*
401 			 * For functions (global vars are only inlined if already static),
402 			 * mark imported variables as being clones from other
403 			 * functions. That a) avoids symbol conflicts b) allows the
404 			 * optimizer to perform inlining.
405 			*/
406 			if (llvm::isa<llvm::Function>(valueToImport))
407 			{
408 				llvm::Function *F = llvm::dyn_cast<llvm::Function>(valueToImport);
409 				typedef llvm::GlobalValue::LinkageTypes LinkageTypes;
410 
411 				/*
412 				 * Per-function info isn't necessarily stripped yet, as the
413 				 * module is lazy-loaded when stripped above.
414 				 */
415 				llvm::stripDebugInfo(*F);
416 
417 				/*
418 				 * If the to-be-imported function is one referenced including
419 				 * its module name, create a tiny inline function that just
420 				 * forwards the call. One might think a GlobalAlias would do
421 				 * the trick, but a) IRMover doesn't override a declaration
422 				 * with an alias pointing to a definition (instead renaming
423 				 * it), b) Aliases can't be AvailableExternally.
424 				 */
425 				if (modname)
426 				{
427 					llvm::Function *AF;
428 
429 					AF = create_redirection_function(importMod, F, SymbolName);
430 
431 					GlobalsToImport.insert(AF);
432 					llvm::stripDebugInfo(*AF);
433 				}
434 
435 				if (valueToImport->hasExternalLinkage())
436 				{
437 					valueToImport->setLinkage(LinkageTypes::AvailableExternallyLinkage);
438 				}
439 			}
440 
441 			GlobalsToImport.insert(valueToImport);
442 			ilog(DEBUG1, "performing import of %s %s",
443 				 modPath.data(), SymbolName.data());
444 
445 		}
446 
447 #if LLVM_VERSION_MAJOR > 4
448 #define IRMOVE_PARAMS , /*IsPerformingImport=*/false
449 #elif LLVM_VERSION_MAJOR > 3
450 #define IRMOVE_PARAMS , /*LinkModuleInlineAsm=*/false, /*IsPerformingImport=*/false
451 #else
452 #define IRMOVE_PARAMS
453 #endif
454 		if (Mover.move(std::move(importMod), GlobalsToImport.getArrayRef(),
455 					   [](llvm::GlobalValue &, llvm::IRMover::ValueAdder) {}
456 					   IRMOVE_PARAMS))
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*
load_module_cached(llvm::StringRef modPath)468 load_module_cached(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(modPath))).first;
475 	}
476 
477 	return it->second.get();
478 }
479 
480 static std::unique_ptr<llvm::Module>
load_module(llvm::StringRef Identifier)481 load_module(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(LLVMGetGlobalContext(), 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
function_references(llvm::Function & F,int & running_instcount,llvm::SmallPtrSet<llvm::GlobalVariable *,8> & referencedVars,llvm::SmallPtrSet<llvm::Function *,8> & referencedFunctions)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
function_inlinable(llvm::Function & F,int threshold,FunctionInlineStates & functionStates,InlineWorkList & worklist,InlineSearchPath & searchpath,llvm::SmallPtrSet<const llvm::Function *,8> & visitedFunctions,int & running_instcount,llvm::StringSet<> & importVars)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().hasFnAttribute(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 dependants */
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>
llvm_load_summary(llvm::StringRef path)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 #if LLVM_VERSION_MAJOR > 3
779 		llvm::Expected<std::unique_ptr<llvm::ModuleSummaryIndex> > IndexOrErr =
780 			llvm::getModuleSummaryIndex(ref);
781 		if (IndexOrErr)
782 			return std::move(IndexOrErr.get());
783 		elog(FATAL, "failed to load summary \"%s\": %s",
784 			 path.data(),
785 			 toString(IndexOrErr.takeError()).c_str());
786 #else
787 		llvm::ErrorOr<std::unique_ptr<llvm::ModuleSummaryIndex> > IndexOrErr =
788 			llvm::getModuleSummaryIndex(ref, [](const llvm::DiagnosticInfo &) {});
789 		if (IndexOrErr)
790 			return std::move(IndexOrErr.get());
791 		elog(FATAL, "failed to load summary \"%s\": %s",
792 			 path.data(),
793 			 IndexOrErr.getError().message().c_str());
794 #endif
795 	}
796 	return nullptr;
797 }
798 
799 /*
800  * Attempt to add modpath to the search path.
801  */
802 static void
add_module_to_inline_search_path(InlineSearchPath & searchpath,llvm::StringRef modpath)803 add_module_to_inline_search_path(InlineSearchPath& searchpath, llvm::StringRef modpath)
804 {
805 	/* only extension in libdir are candidates for inlining for now */
806 	if (!modpath.startswith("$libdir/"))
807 		return;
808 
809 	/* if there's no match, attempt to load */
810 	auto it = summary_cache->find(modpath);
811 	if (it == summary_cache->end())
812 	{
813 		std::string path(modpath);
814 		path = path.replace(0, strlen("$libdir"), std::string(pkglib_path) + "/bitcode");
815 		path += ".index.bc";
816 		(*summary_cache)[modpath] = llvm_load_summary(path);
817 		it = summary_cache->find(modpath);
818 	}
819 
820 	Assert(it != summary_cache->end());
821 
822 	/* if the entry isn't NULL, it's validly loaded */
823 	if (it->second)
824 		searchpath.push_back(it->second.get());
825 }
826 
827 /*
828  * Search for all references for functions hashing to guid in the search path,
829  * and return them in search path order.
830  */
831 static llvm::SmallVector<llvm::GlobalValueSummary *, 1>
summaries_for_guid(const InlineSearchPath & path,llvm::GlobalValue::GUID guid)832 summaries_for_guid(const InlineSearchPath& path, llvm::GlobalValue::GUID guid)
833 {
834 	llvm::SmallVector<llvm::GlobalValueSummary *, 1> matches;
835 
836 	for (auto index : path)
837 	{
838 #if LLVM_VERSION_MAJOR > 4
839 		llvm::ValueInfo funcVI = index->getValueInfo(guid);
840 
841 		/* if index doesn't know function, we don't have a body, continue */
842 		if (funcVI)
843 			for (auto &gv : funcVI.getSummaryList())
844 				matches.push_back(gv.get());
845 #else
846 		const llvm::const_gvsummary_iterator &I =
847 			index->findGlobalValueSummaryList(guid);
848 		if (I != index->end())
849 		{
850 			for (auto &gv : I->second)
851 				matches.push_back(gv.get());
852 		}
853 #endif
854 	}
855 
856 	return matches;
857 }
858 
859 /*
860  * Create inline wrapper with the name Name, redirecting the call to F.
861  */
862 static llvm::Function*
create_redirection_function(std::unique_ptr<llvm::Module> & importMod,llvm::Function * F,llvm::StringRef Name)863 create_redirection_function(std::unique_ptr<llvm::Module> &importMod,
864 							llvm::Function *F,
865 							llvm::StringRef Name)
866 {
867 	typedef llvm::GlobalValue::LinkageTypes LinkageTypes;
868 
869 	llvm::LLVMContext &Context = F->getContext();
870 	llvm::IRBuilder<> Builder(Context);
871 	llvm::Function *AF;
872 	llvm::BasicBlock *BB;
873 	llvm::CallInst *fwdcall;
874 	llvm::Attribute inlineAttribute;
875 
876 	AF = llvm::Function::Create(F->getFunctionType(),
877 								LinkageTypes::AvailableExternallyLinkage,
878 								Name, importMod.get());
879 	BB = llvm::BasicBlock::Create(Context, "entry", AF);
880 
881 	Builder.SetInsertPoint(BB);
882 	fwdcall = Builder.CreateCall(F, &*AF->arg_begin());
883 	inlineAttribute = llvm::Attribute::get(Context,
884 										   llvm::Attribute::AlwaysInline);
885 	fwdcall->addAttribute(~0U, inlineAttribute);
886 	Builder.CreateRet(fwdcall);
887 
888 	return AF;
889 }
890