devbox
羊村懒王
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：羊村懒王 | 2024-05-15 13:27:40

赞

踩

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（...)
{
	...

  • 1
  • 2
  • 3
  • 弱定义函数，__attribute__((weak))，不会Inline。
	if (F.isInterposable())
		return false;

  • 1
  • 2
  • 通常指的是C代码中有inline关键字的函数，不需要这里再inline了。
	if (F.hasAvailableExternallyLinkage())
		return false;

  • 1
  • 2
  • 把函数从IR文件加载到内存中使用。
	if (F.materialize())
		elog(FATAL, "failed to materialize metadata");


  • 1
  • 2
  • 3
  • 确定函数没有NoInline属性（后文有个例子）。
	if (F.getAttributes().hasFnAttr(llvm::Attribute::NoInline))
	{
		ilog(DEBUG1, "ineligibile to import %s due to noinline",
			 F.getName().data());
		return false;
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • function_references目的是为了了解当前函数引用了哪些变量和其他函数，评估它的大致复杂度。
  • 这里以 dexp函数为例展开讲下function_references的流程：
	function_references(F, running_instcount, referencedVars, referencedFunctions);

  • 1

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
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60

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)
{

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 申请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;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 申请8个位置的vector存放llvm::User指针（Instruction的基类）：
			llvm::SmallVector<llvm::User *, 8> Worklist;
			Worklist.push_back(&I);


  • 1
  • 2
  • 3
  • 指令计数running_instcount（Instruction的基类）：
			running_instcount++;

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


  • 1
  • 2
  • 3
  • 4
  • 5
  • 这条指令之前有没有被记录过：
				if (!Visited.insert(U).second)
					continue;

  • 1
  • 2
  • 遍历Instruction的操作数operands，操作数的基类也是User：
				for (auto &OI : U->operands()) {
					llvm::User *Operand = llvm::dyn_cast<llvm::User>(OI);
					if (!Operand)
						continue;

  • 1
  • 2
  • 3
  • 4
  • 当前拿到的操作数是一个baseblock的地址，一般是用于跳转，不需要记录：
					if (llvm::isa<llvm::BlockAddress>(Operand))
						continue;

  • 1
  • 2
  • 这里看到一个全局变量，需要记录到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;
					}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 这里发现一个操作数是另一个函数，说明有其他函数引用，将Function指针记录到referencedFunctions中。
					if (auto *CF = llvm::dyn_cast<llvm::Function>(Operand)) {
						referencedFunctions.insert(CF);
						continue;
					}
					Worklist.push_back(Operand);
				}
			}
		}
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

执行结束后：

  • 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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

定义

$ 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
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 引用函数个数：去重后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;
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 标记当前函数已经处理过了：
	visitedFunctions.insert(&F);

  • 1
  • 检查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");

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 判断是不是llvm内建函数，例如循环给数组赋零有可能被clang在-O2时被优化为llvm.memset
  • dexp调用的五个函数中，只有llvm.fabs.f64是llvm内建函数：
		if (referencedFunction->isIntrinsic())
			continue;


  • 1
  • 2
  • 3
  • 已经处理过了？
		if (!visitedFunctions.insert(referencedFunction).second)
			continue;


  • 1
  • 2
  • 3
  • 当前函数在其他编译单元？
  • 例如__errno_location函数就在glibc中。
		if (referencedFunction->hasExternalLinkage())
		{
			llvm::StringRef funcName = referencedFunction->getName();

			/*
			 * Don't bother checking for inlining if remaining cost budget is
			 * very small.
			 */

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 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())
			{

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 注意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);
			}
			...
	

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 弱定义函数，__attribute__((weak))，排除。
		if (referencedFunction->isInterposable())
			return false;


  • 1
  • 2
  • 3
  • 递归调用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());
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

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

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

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

	return true;
}

  • 1
  • 2

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)))))

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

这里函数被标记了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);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

原因是这里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)))))

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/573056
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号