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

mingjie

发布于 2024-05-09 08:21:12

930

发布于 2024-05-09 08:21:12

文章被收录于专栏：Postgresql源码分析

在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+00
  br i1 %5, label %28, label %6

6:                                                ; preds = %1
  %7 = tail call double @llvm.fabs.f64(double %4) #22
  %8 = fcmp oeq double %7, 0x7FF0000000000000
  br i1 %8, label %9, label %12

9:                                                ; preds = %6
  %10 = fcmp ogt double %4, 0.000000e+00
  %11 = select i1 %10, double %4, double 0.000000e+00
  br label %28

12:                                               ; preds = %6
  %13 = tail call ptr @__errno_location() #23
  store 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, 34
  br i1 %16, label %17, label %21, !prof !11

17:                                               ; preds = %12
  %18 = fcmp une double %14, 0.000000e+00
  br i1 %18, label %19, label %20

19:                                               ; preds = %17
  tail call void @float_overflow_error() #24
  unreachable

20:                                               ; preds = %17
  tail call void @float_underflow_error() #24
  unreachable

21:                                               ; preds = %12
  %22 = tail call double @llvm.fabs.f64(double %14) #22
  %23 = fcmp oeq double %22, 0x7FF0000000000000
  br i1 %23, label %24, label %25, !prof !11

24:                                               ; preds = %21
  tail call void @float_overflow_error() #24
  unreachable

25:                                               ; preds = %21
  %26 = fcmp oeq double %14, 0.000000e+00
  br i1 %26, label %27, label %28, !prof !11

27:                                               ; preds = %25
  tail call void @float_underflow_error() #24
  unreachable

28:                                               ; preds = %25, %9, %1
  %29 = phi double [ %11, %9 ], [ %14, %25 ], [ %4, %1 ]
  %30 = bitcast double %29 to i64
  ret 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+00
  br i1 %5, label %28, label %6

6:                                                ; preds = %1
  %7 = tail call double @llvm.fabs.f64(double %4) #22
  %8 = fcmp oeq double %7, 0x7FF0000000000000
  br i1 %8, label %9, label %12

9:                                                ; preds = %6
  %10 = fcmp ogt double %4, 0.000000e+00
  %11 = select i1 %10, double %4, double 0.000000e+00
  br label %28

12:                                               ; preds = %6
  %13 = tail call ptr @__errno_location() #23
  store 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, 34
  br i1 %16, label %17, label %21, !prof !11

17:                                               ; preds = %12
  %18 = fcmp une double %14, 0.000000e+00
  br i1 %18, label %19, label %20

19:                                               ; preds = %17
  tail call void @float_overflow_error() #24
  unreachable

20:                                               ; preds = %17
  tail call void @float_underflow_error() #24
  unreachable

21:                                               ; preds = %12
  %22 = tail call double @llvm.fabs.f64(double %14) #22
  %23 = fcmp oeq double %22, 0x7FF0000000000000
  br i1 %23, label %24, label %25, !prof !11

24:                                               ; preds = %21
  tail call void @float_overflow_error() #24
  unreachable

25:                                               ; preds = %21
  %26 = fcmp oeq double %14, 0.000000e+00
  br i1 %26, label %27, label %28, !prof !11

27:                                               ; preds = %25
  tail call void @float_underflow_error() #24
  unreachable

28:                                               ; preds = %25, %9, %1
  %29 = phi double [ %11, %9 ], [ %14, %25 ], [ %4, %1 ]
  %30 = bitcast double %29 to i64
  ret 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();
			else
				float_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)))))

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-05-08，如有侵权请联系 cloudcommunity@tencent.com 删除

jit