当前位置：首页 > news >正文

NonDefUseDependency及例子

news 来源：原创 2024/5/13 6:01:12

在研究ReassociatePass的优化时，我发现了其中有一个函数bool llvm::mayHaveNonDefUseDependency(const Instruction &I) {，这个函数会判断一个指令是否是不可优化的，也即是否是可能会造成NonDefUseDependency的。
潜在的非定义使用依赖关系指的是在程序中，某个指令使用了另一个指令产生的值，但两者之间的关系不是经过明确定义的。这可能导致程序在并行执行或重排序时出现问题，因为执行顺序的改变可能会影响到数据的正确性。
这种所谓的没有经过明确定义的，也即没有通过限制指令标记两个指令之间是不可移动或不可并行的，但两个指令之间有明显的先后关系，如果并行可能会出现某种失败的情况。

一个例子

#include <iostream>
#include <omp.h>int main() {int x = 0;#pragma omp parallel{#pragma omp forfor(int i = 0; i < 100; ++i)x = x + 1;}std::cout << x << std::endl;
}

omp.h头文件主要是将#pragma omp编译为openmp代码。运行指令如下：

clang -fopenmp source -o target

mayHaveNonDefUseDependency

bool llvm::mayHaveNonDefUseDependency(const Instruction &I) {if (I.mayReadOrWriteMemory())// Memory dependency possiblereturn true;if (!isSafeToSpeculativelyExecute(&I))// Can't move above a maythrow call or infinite loop.  Or if an// inalloca alloca, above a stacksave call.return true;if (!isGuaranteedToTransferExecutionToSuccessor(&I))// 1) Can't reorder two inf-loop calls, even if readonly// 2) Also can't reorder an inf-loop call below a instruction which isn't//    safe to speculative execute.  (Inverse of above)return true;return false;
}

首先判断是否读写内存，常见的例如Load Store指令，Call, Invoke指令。
判断是否是safeToSpeculativelyExecute，此处指的是不能安全的推断执行的指令。能够推测执行的指令，例如如果除数为0，则会返回false，也即mayHaveNonDefUseDependency会返回true.
判断GuaranteedtoTransferExecutionToSuccessor，该函数用于判断一个指令是否可以将控制流转移到指令后。如果是Return指令或不可达指令，显然会返回false。如果是CatchPad指令，需要判断。最后判断指令是否mayThrow或者willReturn，如果不满足mayThro且willReturn，就会返回true.

bool llvm::isGuaranteedToTransferExecutionToSuccessor(const Instruction *I) {// Note: An atomic operation isn't guaranteed to return in a reasonable amount// of time because it's possible for another thread to interfere with it for an// arbitrary length of time, but programs aren't allowed to rely on that.// If there is no successor, then execution can't transfer to it.if (isa<ReturnInst>(I))return false;if (isa<UnreachableInst>(I))return false;// Note: Do not add new checks here; instead, change Instruction::mayThrow or// Instruction::willReturn.//// FIXME: Move this check into Instruction::willReturn.if (isa<CatchPadInst>(I)) { switch (classifyEHPersonality(I->getFunction()->getPersonalityFn())) {default:// A catchpad may invoke exception object constructors and such, which// in some languages can be arbitrary code, so be conservative by default.return false;case EHPersonality::CoreCLR:// For CoreCLR, it just involves a type test.return true;}}// An instruction that returns without throwing must transfer control flow// to a successor.return !I->mayThrow() && I->willReturn();
}