BasicAA fails to return NoAlias from aliasGEP with PHI index. Let's see code snippet.
typedef struct data
{
int oldVal;
int newVal;
} data_t;
void alias_issue(data_t *data, int max) {
int pos = 1;
int cmp = 3;
while(cmp < max) {
data[pos].newVal = data[cmp].newVal;
data[pos].oldVal = data[cmp].newVal;
pos = cmp;
cmp *= 2;
}
return;
}From above code, we can imagine that we need to load data[cmp].newVal one time. Let's see LLVM IR output from above code.
while.cond: ; preds = %while.body, %entry %pos.0 = phi i32 [ 1, %entry ], [ %cmp.0, %while.body ] %cmp.0 = phi i32 [ 3, %entry ], [ %mul, %while.body ] %cmp1 = icmp slt i32 %cmp.0, %max br i1 %cmp1, label %while.body, label %while.end while.body: ; preds = %while.cond %sub = add nsw i32 %cmp.0, -1 %idxprom = sext i32 %sub to i64 %newVal = getelementptr inbounds %struct.data, %struct.data* %data, i64 %idxprom, i32 1 %0 = load i32, i32* %newVal, align 4, !tbaa !6 ==> data[cmp].newVal %sub2 = add nsw i32 %pos.0, -1 %idxprom3 = sext i32 %sub2 to i64 %arrayidx4 = getelementptr inbounds %struct.data, %struct.data* %data, i64 %idxprom3 %newVal5 = getelementptr inbounds %struct.data, %struct.data* %data, i64 %idxprom3, i32 1 store i32 %0, i32* %newVal5, align 4, !tbaa !6 ==> data[pos].newVal = data[cmp].newVal; %1 = load i32, i32* %newVal, align 4, !tbaa !6 ==> data[cmp].newVal %oldVal = getelementptr inbounds %struct.data, %struct.data* %arrayidx4, i32 0, i32 0 store i32 %1, i32* %oldVal, align 4, !tbaa !11 %mul = mul nsw i32 %cmp.0, 2 br label %while.cond
As you can see, there are %0 and %1 which are same load instruction for data[cmp].newVal. Optimization passes like instcombine, GVN check the the address of store i32 %0, i32* %newVal5, align 4, !tbaa !6 has alias with %1 load. BasicAA returns MayAlias for it. If GEP has index with PHI, it look aliasGEP fails to detect NoAlias. Let's see the situation.
loop: %pos.0 = phi i32 [ 1, %entry ], [ %cmp.0, %loop ] %cmp.0 = phi i32 [ 3, %entry ], [ %mul, %loop ] ... %sub = add nsw i32 %cmp.0, -1 %idxprom = sext i32 %sub to i64 %newVal = getelementptr inbounds %struct.data, %struct.data* %data, i64 %idxprom, i32 1 ... %sub2 = add nsw i32 %pos.0, -1 %idxprom3 = sext i32 %sub2 to i64 %newVal5 = getelementptr inbounds %struct.data, %struct.data* %data, i64 %idxprom3, i32 1 ... %mul = mul nsw i32 %cmp.0, 2 br label %loop
On above example, %pos.0 uses previous iteration's %cmp.0 with backedge according to PHI's instruction's definition. In this case, I think we can say %pos.0 is not same with %cmp.0. This patch is to detect above pattern.
clang-tidy: warning: invalid case style for variable 'i' [readability-identifier-naming]
not useful
clang-tidy: warning: invalid case style for variable 'e' [readability-identifier-naming]
not useful