Postgresql中JIT函数能否inline的依据function_inlinable

相关
《Postgresql源码（128）深入分析JIT中的函数内联llvm_inline》
《LLVM的ThinLTO编译优化技术在Postgresql中的应用》

前置阅读：《Postgresql源码（128）深入分析JIT中的函数内联llvm_inline》

在JIT inline函数的过程中，会通过函数的bc代码，经过一系列规则、成本的判断来决定函数能否Inline，本篇重点分析这段逻辑：function_inlinable。

总结速查：

• 入参F（llvm::Function）：待inline函数
• 入参functionStates（数组）：记录了表达式计算所需要的所有函数，在function_inlinable函数内部检查的过程中，函数调用的其他函数，能inline的也会被加到这个数组中。
• 入参worklist（数组）：记录了待处理的{函数名，搜索路径}，包括本次表达式计算的函数 和 在function_inlinable函数内部检查的过程中，函数调用的其他函数。
• 入参visitedFunctions（llvm::Function的SET）：处理过的函数名。
• 入参running_instcount：经过function_inlinable的dfs搜索，包括当前函数和所有被调用者的指令数的总和。
• 入参importVars（String SET ）：全局变量 和 当前函数调用的其他函数的函数名，类似于符号表。

function_inlinable会做dfs搜索所有调用到的函数，关心函数的指令数、里面用到的全局变量的个数。

1 function_inlinable part 1

function_inlinable（...)
{...

• 弱定义函数，__attribute__((weak))，不会Inline。

	if (F.isInterposable())return false;

• 通常指的是C代码中有inline关键字的函数，不需要这里再inline了。

	if (F.hasAvailableExternallyLinkage())return false;

• 把函数从IR文件加载到内存中使用。

	if (F.materialize())elog(FATAL, "failed to materialize metadata");

• 确定函数没有NoInline属性（后文有个例子）。

	if (F.getAttributes().hasFnAttr(llvm::Attribute::NoInline)){ilog(DEBUG1, "ineligibile to import %s due to noinline",F.getName().data());return false;}

• function_references目的是为了了解当前函数引用了哪些变量和其他函数，评估它的大致复杂度。
• 这里以 dexp函数为例展开讲下function_references的流程：

	function_references(F, running_instcount, referencedVars, referencedFunctions);

2 function_references

2.1 基础知识

• BasicBlock 表示的是基本块类，Arugument 表示的是函数的形参，Constant 表示的是形如 i32 4 的常量，Instruction 表示的是形如 add i32 %a,%b 的指令。
• Value 是一个非常基础的基类，一个继承于 Value 的子类表示它的结果可以被其他地方使用。
• User代表了任何可以拥有操作数的LLVM对象。例如%1 = add i32 %a, %b是Instruction，同时也是一个User，抽象理解就是拥有操作数的一切对象都是User。
  

2.2 dexp的ir

定义：

; Function Attrs: nounwind uwtable
define dso_local i64 @dexp(ptr nocapture noundef readonly %0) local_unnamed_addr #6 {%2 = getelementptr inbounds %struct.FunctionCallInfoBaseData, ptr %0, i64 0, i32 6, i64 0, i32 0%3 = bitcast ptr %2 to ptr%4 = load double, ptr %3, align 8%5 = fcmp uno double %4, 0.000000e+00br i1 %5, label %28, label %66:                                                ; preds = %1%7 = tail call double @llvm.fabs.f64(double %4) #22%8 = fcmp oeq double %7, 0x7FF0000000000000br i1 %8, label %9, label %129:                                                ; preds = %6%10 = fcmp ogt double %4, 0.000000e+00%11 = select i1 %10, double %4, double 0.000000e+00br label %2812:                                               ; preds = %6%13 = tail call ptr @__errno_location() #23store i32 0, ptr %13, align 4%14 = tail call double @exp(double noundef %4) #20%15 = load i32, ptr %13, align 4%16 = icmp eq i32 %15, 34br i1 %16, label %17, label %21, !prof !1117:                                               ; preds = %12%18 = fcmp une double %14, 0.000000e+00br i1 %18, label %19, label %2019:                                               ; preds = %17tail call void @float_overflow_error() #24unreachable20:                                               ; preds = %17tail call void @float_underflow_error() #24unreachable21:                                               ; preds = %12%22 = tail call double @llvm.fabs.f64(double %14) #22%23 = fcmp oeq double %22, 0x7FF0000000000000br i1 %23, label %24, label %25, !prof !1124:                                               ; preds = %21tail call void @float_overflow_error() #24unreachable25:                                               ; preds = %21%26 = fcmp oeq double %14, 0.000000e+00br i1 %26, label %27, label %28, !prof !1127:                                               ; preds = %25tail call void @float_underflow_error() #24unreachable28:                                               ; preds = %25, %9, %1%29 = phi double [ %11, %9 ], [ %14, %25 ], [ %4, %1 ]%30 = bitcast double %29 to i64ret i64 %30
}

2.3 function_references函数

static void
function_references(llvm::Function &F,int &running_instcount,llvm::SmallPtrSet<llvm::GlobalVariable *, 8> &referencedVars,llvm::SmallPtrSet<llvm::Function *, 8> &referencedFunctions)
{

• 申请32个位置的Set存放User指针，具体就是Instruction

	llvm::SmallPtrSet<const llvm::User *, 32> Visited;for (llvm::BasicBlock &BB : F){for (llvm::Instruction &I : BB){if (llvm::isa<llvm::DbgInfoIntrinsic>(I))continue;

• 申请8个位置的vector存放llvm::User指针（Instruction的基类）：

			llvm::SmallVector<llvm::User *, 8> Worklist;Worklist.push_back(&I);

• 指令计数running_instcount（Instruction的基类）：

			running_instcount++;while (!Worklist.empty()) {llvm::User *U = Worklist.pop_back_val();

• 这条指令之前有没有被记录过：

				if (!Visited.insert(U).second)continue;

• 遍历Instruction的操作数operands，操作数的基类也是User：

				for (auto &OI : U->operands()) {llvm::User *Operand = llvm::dyn_cast<llvm::User>(OI);if (!Operand)continue;

• 当前拿到的操作数是一个baseblock的地址，一般是用于跳转，不需要记录：

					if (llvm::isa<llvm::BlockAddress>(Operand))continue;

• 这里看到一个全局变量，需要记录到referencedVars中，并把全局变量的定义拿出来，放到Worklist里面去统计一把，比如一个全局变量定义为int a = 1，那么这一个Instruction会在下一轮循环中被统计。

					if (auto *GV = llvm::dyn_cast<llvm::GlobalVariable>(Operand)) {referencedVars.insert(GV);if (GV->hasInitializer())Worklist.push_back(GV->getInitializer());continue;}

• 这里发现一个操作数是另一个函数，说明有其他函数引用，将Function指针记录到referencedFunctions中。

					if (auto *CF = llvm::dyn_cast<llvm::Function>(Operand)) {referencedFunctions.insert(CF);continue;}Worklist.push_back(Operand);}}}}
}

执行结束后：

• running_instcount：35
  • IR中有35个指令
• referencedVars：空
• referencedFunctions：5个函数

dexp函数的IR分两部分：函数摘要和函数定义（index文件就是收集了bc文件中的函数摘要）

摘要：

^62 = gv: (name: "dexp", summaries: (function: (module: ^0, flags: (linkage: external, visibility: default, notEligibleToImport: 0, live: 0, dsoLocal: 1, canAutoHide: 0), insts: 35, funcFlags: (readNone: 0, readOnly: 0, noRecurse: 0, returnDoesNotAlias: 0, noInline: 0, alwaysInline: 0, noUnwind: 1, mayThrow: 0, hasUnknownCall: 0, mustBeUnreachable: 0), calls: ((callee: ^302), (callee: ^157), (callee: ^277), (callee: ^54))))) ; guid = 3352526880228194314

定义

$ cat float.ll | grep -A 58 '@dexp'
define dso_local i64 @dexp(ptr nocapture noundef readonly %0) local_unnamed_addr #6 {%2 = getelementptr inbounds %struct.FunctionCallInfoBaseData, ptr %0, i64 0, i32 6, i64 0, i32 0%3 = bitcast ptr %2 to ptr%4 = load double, ptr %3, align 8%5 = fcmp uno double %4, 0.000000e+00br i1 %5, label %28, label %66:                                                ; preds = %1%7 = tail call double @llvm.fabs.f64(double %4) #22%8 = fcmp oeq double %7, 0x7FF0000000000000br i1 %8, label %9, label %129:                                                ; preds = %6%10 = fcmp ogt double %4, 0.000000e+00%11 = select i1 %10, double %4, double 0.000000e+00br label %2812:                                               ; preds = %6%13 = tail call ptr @__errno_location() #23store i32 0, ptr %13, align 4%14 = tail call double @exp(double noundef %4) #20%15 = load i32, ptr %13, align 4%16 = icmp eq i32 %15, 34br i1 %16, label %17, label %21, !prof !1117:                                               ; preds = %12%18 = fcmp une double %14, 0.000000e+00br i1 %18, label %19, label %2019:                                               ; preds = %17tail call void @float_overflow_error() #24unreachable20:                                               ; preds = %17tail call void @float_underflow_error() #24unreachable21:                                               ; preds = %12%22 = tail call double @llvm.fabs.f64(double %14) #22%23 = fcmp oeq double %22, 0x7FF0000000000000br i1 %23, label %24, label %25, !prof !1124:                                               ; preds = %21tail call void @float_overflow_error() #24unreachable25:                                               ; preds = %21%26 = fcmp oeq double %14, 0.000000e+00br i1 %26, label %27, label %28, !prof !1127:                                               ; preds = %25tail call void @float_underflow_error() #24unreachable28:                                               ; preds = %25, %9, %1%29 = phi double [ %11, %9 ], [ %14, %25 ], [ %4, %1 ]%30 = bitcast double %29 to i64ret i64 %30
}

• 引用函数个数：去重后5个
• 指令个数：35
  
• 引用全局变量个数：0个

和function_references计算结果一致。

3 function_inlinable part 2

• 记录全局变量到importVars，并增加成本：

	for (llvm::GlobalVariable* rv: referencedVars){...importVars.insert(rv->getName());/* small cost attributed to each cloned global */running_instcount += 5;}

• 标记当前函数已经处理过了：

	visitedFunctions.insert(&F);

• 检查dexp调用的函数：这里会处理5个函数：
  • llvm.fabs.f64
  • __errno_location
  • exp
  • float_overflow_error
  • float_underflow_error

	for (llvm::Function* referencedFunction: referencedFunctions){llvm::StringSet<> recImportVars;if (referencedFunction->materialize())elog(FATAL, "failed to materialize metadata");

• 判断是不是llvm内建函数，例如循环给数组赋零有可能被clang在-O2时被优化为llvm.memset
• dexp调用的五个函数中，只有llvm.fabs.f64是llvm内建函数：

		if (referencedFunction->isIntrinsic())continue;

• 已经处理过了？

		if (!visitedFunctions.insert(referencedFunction).second)continue;

• 当前函数在其他编译单元？
• 例如__errno_location函数就在glibc中。

		if (referencedFunction->hasExternalLinkage()){llvm::StringRef funcName = referencedFunction->getName();/** Don't bother checking for inlining if remaining cost budget is* very small.*/

• inline_initial_cost默认给150。
• subThreshold = inline_initial_cost * inline_cost_decay_factor = 150 * 0.5 = 75

			if (subThreshold < 5)continue;auto it = functionStates.find(funcName);if (it == functionStates.end()){

• 注意functionStates数组里面包含本次表达式计算用到的所有函数，比如int4abs、dexp、slot_getsomeattrs_int、i4tod等等。
• 这里会把需要inline的函数加到functionStates中，先不做其他处理。

				FunctionInlineState inlineState;inlineState.costLimit = subThreshold;inlineState.processed = false;inlineState.inlined = false;inlineState.allowReconsidering = false;functionStates[funcName] = inlineState;worklist.push_back({funcName, searchpath});ilog(DEBUG1,"considering extern function %s at %d for inlining",funcName.data(), subThreshold);}...

• 弱定义函数，__attribute__((weak))，排除。

		if (referencedFunction->isInterposable())return false;

• 递归调用function_inlinable，检查内层函数。

		if (!function_inlinable(*referencedFunction,subThreshold,functionStates,worklist,searchpath,visitedFunctions,running_instcount,recImportVars)){return false;}/* import referenced function itself */importVars.insert(referencedFunction->getName());/* import referenced function and its dependents */for (auto& recImportVar : recImportVars)importVars.insert(recImportVar.first());}

经过function_inlinable的递归调用，dfs所有会调用到的函数，最终：

• 需要inline的函数已经都加入到functionStates中。
• 需要Inline的{函数名字，搜索路径}在worklist中。
• 函数名和全局变量名，全部加入到worklist。

返回true表示当前函数可以inline。

	return true;
}

4 其他

dexp

怎么拿到函数的guid：funcGUID = llvm::GlobalValue::getGUID(cfuncname);
（GUID是用函数名MD5 hash出来的）
funcGUID = 3352526880228194314

index文件中查看函数属性：

^12463 = gv: (guid: 3352526880228194314, summaries: (function: (module: ^604, flags: (linkage: external, visibility: default, notEligibleToImport: 0, live: 0, dsoLocal: 1, canAutoHide: 0), insts: 79, funcFlags: (readNone: 0, readOnly: 0, noRecurse: 0, returnDoesNotAlias: 0, noInline: 1, alwaysInline: 0, noUnwind: 1, mayThrow: 0, hasUnknownCall: 0, mustBeUnreachable: 0), calls: ((callee: ^6190), (callee: ^59633), (callee: ^10786), (callee: ^32543)))))

这里函数被标记了noInline: 1，所以该函数不会被inline。

但是dexp为什么不能被inline呢？看起来函数不长，分支也不多，也没有标记__attribute__((noinline))。

Datum
dexp(PG_FUNCTION_ARGS)
{float8		arg1 = PG_GETARG_FLOAT8(0);float8		result;if (isnan(arg1))result = arg1;else if (isinf(arg1)){/* Per POSIX, exp(-Inf) is 0 */result = (arg1 > 0.0) ? arg1 : 0;}else{errno = 0;result = exp(arg1);if (unlikely(errno == ERANGE)){if (result != 0.0)float_overflow_error();elsefloat_underflow_error();}else if (unlikely(isinf(result)))float_overflow_error();else if (unlikely(result == 0.0))float_underflow_error();}PG_RETURN_FLOAT8(result);
}

原因是这里llvm是按O2编译的，按O0编译后noInline: 0

^10363 = gv: (guid: 3352526880228194314, summaries: (function: (module: ^604, flags: (linkage: external, visibility: default, notEligibleToImport: 0, live: 0, dsoLocal: 1, canAutoHide: 0), insts: 35, funcFlags: (readNone: 0, readOnly: 0, noRecurse: 0, returnDoesNotAlias: 0, noInline: 0, alwaysInline: 0, noUnwind: 1, mayThrow: 0, hasUnknownCall: 0, mustBeUnreachable: 0), calls: ((callee: ^49065), (callee: ^8990)))))