错误的 LLVM 别名分析

Question

我在问一个类似于 this post 的问题，关于 LLVM 别名分析似乎给出了不正确的结果。由于它包含大量重写，我决定 post 它作为一个单独的问题。我是运行这个非常简单的代码：

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 位码：

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

当我查看规格时 the LLVM documentation 中的通行证 -basicaa，它明确表示（强调我的）：

Distinct globals, stack allocations, and heap allocations can never alias.

但这里就是这种情况，有两个不同的堆分配。怎么回事？

编辑:

这是 print-alias-sets 的输出

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%

另一个编辑：

以下是我在（循环）通道中检查别名的方法：

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";
                }
            }
        }
    }

Answer 1

不同的堆分配被正确地视为独立的（即非别名），您可以通过在入口基本块的末尾添加此指令来检查：

%cmp3 = icmp ult i8* %call, %call1

为了正确地进行别名分析 "kick in"，您需要运行优化代码。在这种情况下，还应该添加 -mem2reg。

此外，请确保您正在分析的函数未标记 optnone 属性（反汇编并检查可读的 IR 代码），这将禁用对其的优化。

错误的 LLVM 别名分析

Incorrect LLVM alias analysis

alias

static-analysis

llvm

llvm-ir