LLVM replace pointer arithmetic with array indexing

Question

I would like to use LLVM 3.1 to transform loops using pointer arithmetic to instead use array indexing. For example (shown in C rather than bitcode for clarity):

void f() {
    int buf[10];
    int i;
    int *p = buf;
    for (i = 0; i < 10; i++)
        *p++ = 0;
}

should transform into

void f() {
    int buf[10];
    int i;
    int *p = buf;
    for (i = 0; i < 10; i++)
        p[i] = 0;
}

and

void g(int *p, int n) {
    int *end = p + n;
    for (; p < end, p++)
        *p = 0;
}

should transform into

void g(int *p, int n) {
    int i;
    for (i = 0; i < n, i++)
        p[i] = 0;
}

I have tried using

opt -mem2reg -indvars <bc-file> -S

but I do not see any changes. I do see changes on examples like that in the comment of the IndVarSimplify.cpp file, using only integer loop variables. But I cannot see any examples of pointer arithmetic being raised to use array subscripts, as subscribed in the docs. Is it possible to achieve the results I'm looking for?

Edit:

Below is the bitcode (after mem2reg) for the two "f" functions above. The key difference is the GEP inside the loop, which in the first case is incrementing the pointer from the previous iteration, and in the second case is computing the pointer each time using the base pointer and the index i. This is what I want - to have the address being stored to based on the induction variable i.

Bitcode for first f:

define void @f() nounwind uwtable {
entry:
  %buf = alloca [10 x i32], align 16
  %arraydecay = getelementptr inbounds [10 x i32]* %buf, i32 0, i32 0
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
  %p.0 = phi i32* [ %arraydecay, %entry ], [ %incdec.ptr, %for.inc ]
  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
  %cmp = icmp slt i32 %i.0, 10
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %incdec.ptr = getelementptr inbounds i32* %p.0, i32 1
  store i32 0, i32* %p.0, align 4
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %inc = add nsw i32 %i.0, 1
  br label %for.cond

for.end:                                          ; preds = %for.cond
  ret void
}

Bitcode for second f:

define void @f() nounwind uwtable {
entry:
  %buf = alloca [10 x i32], align 16
  %arraydecay = getelementptr inbounds [10 x i32]* %buf, i32 0, i32 0
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
  %cmp = icmp slt i32 %i.0, 10
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %idxprom = sext i32 %i.0 to i64
  %arrayidx = getelementptr inbounds i32* %arraydecay, i64 %idxprom
  store i32 0, i32* %arrayidx, align 4
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %inc = add nsw i32 %i.0, 1
  br label %for.cond

for.end:                                          ; preds = %for.cond
  ret void
}

I'm not sure that there is an analysis in LLVM which can do this. Could you post the bitcode as well to help us see what the analysis needs to recognise? — James
There is no difference between "pointer arithmetis" and "array indexing" whatsoever. At the IR level, it's all done via the GEP instruction. The only thing I can think of is replacing GEPs with the bounded GEPs, if your static analysis could prove that there is a bound known for this pointer. — SK-logic
@SK-logic: The difference is in the first case the pointer value is updated using a GEP with index 1 in the loop, whereas in the second case the pointer being stored to in the loop is computed as a GEP from p with index i — daniel
@daniel, I'm not sure any such difference would remain after a number of InstCombines. — SK-logic
@SK-logic, thanks for your help, but it's still not producing what I want, i.e. computing the pointer directly from the IV. The command I'm using is "opt -instcombine -instcombine -scalarrepl -instcombine -instcombine -indvars -instcombine -instcombine" (plenty of instcombines just to make sure) is there any other passes that might be needed? — daniel

David Greene David Greene · Accepted Answer · 2014-08-24T04:24:41

There is no LLVM transformation that does this. I wrote my own instcombine transformation to do it.

LLVM replace pointer arithmetic with array indexing

1 Answers