How Should AA Handle This?

IR & Optimizations
1

Consider the following code:

int cond();
int cond2();

struct Str
{
  long l0;
  long l1;
};

void foo(struct Str* arrOfStructs) {
   long i0 = cond2() ? 2 : 3;
   long i1 = 1;

    while(cond()) {
        arrOfStructs[i1].l0 = arrOfStructs[i0].l0;
        arrOfStructs[i1].l1 = arrOfStructs[i0].l0;

        i1 = i0;
        i0 *= 2;
    }

    return;
}

We see that i1 is strictly greater than i0 on each iteration. The IR after EarlyCSE pass looks like this:

define dso_local void @foo(ptr noundef %arrOfStructs) #0 {
entry:
  %call = call signext i32 @cond2()
  %tobool = icmp ne i32 %call, 0
  %cond = select i1 %tobool, i32 2, i32 3
  %conv = sext i32 %cond to i64
  br label %while.cond

while.cond:                                       ; preds = %while.body, %entry
  %i0.0 = phi i64 [ %conv, %entry ], [ %mul, %while.body ]
  %i1.0 = phi i64 [ 1, %entry ], [ %i0.0, %while.body ]
  %call1 = call signext i32 @cond()
  %tobool2 = icmp ne i32 %call1, 0
  br i1 %tobool2, label %while.body, label %while.end

while.body:                                       ; preds = %while.cond
  %arrayidx = getelementptr inbounds %struct.Str, ptr %arrOfStructs, i64 %i0.0
  %0 = load i64, ptr %arrayidx, align 8, !tbaa !7
  %arrayidx3 = getelementptr inbounds %struct.Str, ptr %arrOfStructs, i64 %i1.0
  store i64 %0, ptr %arrayidx3, align 8, !tbaa !7
  %1 = load i64, ptr %arrayidx, align 8, !tbaa !7 ; <-- THIS LOAD IS REDUNDANT
  %l1 = getelementptr inbounds %struct.Str, ptr %arrayidx3, i32 0, i32 1
  store i64 %1, ptr %l1, align 8, !tbaa !12
  %mul = mul nsw i64 %i0.0, 2
  br label %while.cond, !llvm.loop !13

while.end:                                        ; preds = %while.cond
  ret void

Should SCEVAA be able to prove that %arrayidx and arrayidx3 don’t alias? Or maybe basic AA? Any suggestions how to fix this?

Thanks!

2

The general way to handle this would be via isKnownNonEqual(), which is used by BasicAA.

I think it would in principle be capable of determining this, but it will not analyze phi inequalities where full recursion over more than one operand is necessary.

SCEVAA is unlikely to help here, because SCEV primarily reasons about add recurrences, while you have a multiply recurrence here.

3

@nikic Thanks very much! I think I found a fix. There are a couple of issues. I’ll post the MR’s soon.