不正确的LLVM别名分析 [英] Incorrect LLVM alias analysis
问题描述
我要问一个类似于这篇文章的关于LLVM的问题别名分析似乎给出了不正确的结果. 由于包含大量重写， 我决定将其发布为单独的问题. 我正在运行以下非常简单的代码:
I'm asking a question similar to this post about an LLVM alias analysis that seems to give incorrect results. Since it contains considerable re-writing, I have decided to post it as a separate question. I'm running this very simple code:
char *foo()
{
int i;
int size;
char *s=malloc(5);
char *p=malloc(8);
while ((i < size) && (s < p))
{
i--;
}
return NULL;
}
每次我的代码遇到icmp指令时，我都会问
它的操作数可以是彼此的别名.第一次比较
它简单地回答否"，但第二个比较是
%tmp2和%tmp3它回答是.
这是生成的LLVM位代码:
Every time my code runs into an icmp instruction, I ask whether
its operands can be aliases of one another. For the first comparison
it trivially answers no, but for the second comparison between
%tmp2 and %tmp3 it answers yes.
Here is the resulting LLVM bitcode:
; Function Attrs: nounwind uwtable
define internal i8* @foo() #0 {
entry:
%i = alloca i32, align 4
%s = alloca i8*, align 8
%p = alloca i8*, align 8
%size = alloca i32, align 4
%call = call noalias i8* @malloc(i64 8) #3
store i8* %call, i8** %s, align 8
%call1 = call noalias i8* @malloc(i64 13) #3
store i8* %call1, i8** %p, align 8
br label %while.cond
while.cond: ; preds = %while.body, %entry
%tmp = load i32, i32* %i, align 4
%tmp1 = load i32, i32* %size, align 4
%cmp = icmp sgt i32 %tmp, %tmp1
br i1 %cmp, label %land.rhs, label %while.end
land.rhs: ; preds = %while.cond
%tmp2 = load i8*, i8** %p, align 8
%tmp3 = load i8*, i8** %s, align 8
%cmp2 = icmp ult i8* %tmp2, %tmp3
br i1 %cmp2, label %while.body, label %while.end
while.body: ; preds = %land.rhs
%tmp5 = load i32, i32* %i, align 4
%dec = add nsw i32 %tmp5, -1
store i32 %dec, i32* %i, align 4
br label %while.cond
while.end: ; preds = %while.cond, %land.rhs
ret i8* null
}
当我看规格时
它明确表示 LLVM文档中的通行证-basicaa (强调我的):
When I looked at the specifications
of the pass -basicaa in the LLVM documentation, it explicitly says that (emphasis mine):
不同的全局变量，堆栈分配和堆分配绝对不能混叠.
但是这里就是这种情况，有两个不同的堆分配. 发生了什么事?
But this is the case here, with two different heap allocations. What's going on?
编辑:
这是打印别名集的输出
opt -basicaa -aa-eval -globals-aa -scev-aa -loop-simplify -instnamer -print-alias-sets -indvars -simplifycfg -view-cfg -o ./examples/input.ready.bc ./examples/input.bc
Alias Set Tracker: 4 alias sets for 4 pointer values.
AliasSet[0x563ec3312a90, 1] must alias, Mod Pointers: (i32* %argc.addr, 4)
AliasSet[0x563ec3312b30, 1] must alias, Mod Pointers: (i8*** %argv.addr, 8)
AliasSet[0x563ec3312bd0, 1] must alias, Mod/Ref Pointers: (i32* %i, 4)
AliasSet[0x563ec3312c70, 2] may alias, Mod/Ref Pointers: (i8* %arrayidx, 1)
3 Unknown instructions: i8* %call, i32 %call1, i8* %call2
Alias Set Tracker: 3 alias sets for 3 pointer values.
AliasSet[0x563ec3312a90, 1] must alias, Mod/Ref Pointers: (i8** %lp.addr, 8)
AliasSet[0x563ec3312b80, 1] must alias, Mod Pointers: (i32* %size.addr, 4)
AliasSet[0x563ec3312ae0, 1] must alias, Mod/Ref Pointers: (i32* %i, 4)
Alias Set Tracker: 5 alias sets for 4 pointer values.
AliasSet[0x563ec3312b80, 1] may alias, Mod/Ref
2 Unknown instructions: i8* %call, i8* %call1
AliasSet[0x563ec3312bd0, 1] must alias, Mod/Ref Pointers: (i8** %s, 8)
AliasSet[0x563ec33129f0, 1] must alias, Mod/Ref Pointers: (i8** %p, 8)
AliasSet[0x563ec33229c0, 1] must alias, Mod/Ref Pointers: (i32* %i, 4)
AliasSet[0x563ec3322a60, 1] must alias, Ref Pointers: (i32* %size, 4)
===== Alias Analysis Evaluator Report =====
94 Total Alias Queries Performed
73 no alias responses (77.6%)
18 may alias responses (19.1%)
2 partial alias responses (2.1%)
1 must alias responses (1.0%)
Alias Analysis Evaluator Pointer Alias Summary: 77%/19%/2%/1%
54 Total ModRef Queries Performed
17 no mod/ref responses (31.4%)
0 mod responses (0.0%)
3 ref responses (5.5%)
34 mod & ref responses (62.9%)
Alias Analysis Evaluator Mod/Ref Summary: 31%/0%/5%/62%
另一项编辑:
这是我从(循环)传递中检查别名的方法:
Here's how I check for aliasing from within the (Loop) pass:
virtual bool runOnLoop(Loop *loop, LPPassManager &LPM)
{
AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
for (auto it = loop->block_begin(); it != loop->block_end(); it++)
{
for (auto inst = (*it)->begin(); inst != (*it)->end(); inst++)
{
Instruction *i = (Instruction *) inst;
if (strncmp(i->getOpcodeName(),"icmp",4) == 0)
{
CmpInst *ci = (CmpInst *) i;
if (AA->isNoAlias(
ci->getOperand(0),
ci->getOperand(1)))
{
errs() << ci->getOperand(0)->getName().str();
errs() << " and ";
errs() << ci->getOperand(1)->getName().str();
errs() << " are NOT aliases\n";
}
else
{
errs() << ci->getOperand(0)->getName().str();
errs() << " and ";
errs() << ci->getOperand(1)->getName().str();
errs() << " are aliases of one another\n";
}
}
}
}
推荐答案
不同的堆分配被正确地认为是独立的(即非锯齿)，您可以通过在基本条目的末尾添加以下指令来进行检查:
The different heap allocations are correctly regarded as separate (i.e. non-aliasing) and you can check that by adding this instruction at the end of the entry basic block:
%cmp3 = icmp ult i8* %call, %call1
要使别名分析正确地插入"，您需要在优化的代码上运行它.
在这种情况下，也应添加-mem2reg.
For the alias analysis to properly "kick in", you need to run it over optimized code.
In this case also adding -mem2reg should do it.
此外，请确保您要分析的功能未标记有optnone属性(反汇编并检入可读的IR代码)，这将禁用该功能的优化.
Moreover, make sure that the function you're analyzing is not marked with the optnone attribute (disassemble and check in the readable IR code), which will disable optimizations for it.
这篇关于不正确的LLVM别名分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
