Particular type of loop optimization

[Gleison_Souza]

Dear LLVMers,

I am trying to implement a particular type of loop optimization, but I am having problems with global variables. To solve this problem, I would like to know if LLVM has some pass that moves loads outside loops. I will illustrate with an example. I want to transform this code below. I am writing in C for readability, but I am analysing LLVM IR:

int *vectorE;

void foo (int n) {
int i;
for (i = 0; i < n; i++)
vectorE[i] = i;
}

into this one:

int *vectorE;

void foo (int n) {
int i;
int* aux = vectorE;
for (i = 0; i < n; i++)
aux[i] = i;
}

Regards,

Gleison

[mats_petersson]

What are you actually trying to achieve?

I would have thought that [once it gets optimised enough], the compiler does that, or something similar anyway [in particular *aux++ = i; would be what I’d expect to see].

(Obviously, with global variables, there’s always a bit of a problem if the compiler believes that some other code may change vectorE during the execution of foo, and what is expected to happen if that is the case)

[MARCELLO_MAGGIONI1]

Do you have alias analysis enabled?

Marcello

[Gleison_Souza]

Hi all,

Firstly, thanks.

What are you actually trying to achieve?

Please, take a look in the basic block below:

for.body: ; preds = %for.cond
%idxprom = sext i32 %i.0 to i64, !dbg !32
%0 = load i32*, i32** @vectorE, align 8, !dbg !32
%arrayidx = getelementptr inbounds i32, i32* %0, i64 %idxprom, !dbg !32
store i32 %i.0, i32* %arrayidx, align 4, !dbg !33
br label %for.inc, !dbg !32

I need to try remove this load of the loop. If I do this, all loads
of this code can’t generate alias.
running the second code, all loads haven’t alias, like you can see below:

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

I need to reduce the number of alias in the code.

I’ve tried to use this flags:

-mem2reg
-basicaa
-globalsmodref-aa
-tbaa
-scev-aa
-adce
-licm
-argpromotion
-gvn
-memcpyopt
-dse
-print-alias-sets
-count-aa
-aa-eval

Regards,

Gleison

[mehdi_amini]

Have you looked at the output of clang with optimization enabled (even O1)? For this C++ code the optimizer moves the access to the global in the loop preheader, and then the loop itself does not access the global at all, which seems to be what you’re looking for.

Try: clang -O1 -S -o - -mllvm -print-after-all

[Gleison_Souza]

Thanks Mehdi,

I tried to use this, but some debug information can be lost in these optimizations.
I need write in the source file to insert information before the loops, and in
some cases, I’m writing after the loop header.

Please, take a look:

int foo1 (int *a, int *b, int n) {
int i, s= 0;
for (i = 0; i < n; i++) {
s = s * a[i];
}

for (i = 0; i < n; i++) {
b[i] = a[i] + 3;
s += a[i];
}
return s;
}

In this case, using the line obtained by this one in the LLVM’s IR:

Line = l->getStartLoc().getLine();

The source file is cloned, and I’m writing my annotations inside the loop now.
I can’t do several modifications in the struct of code, just the necessary, thats the problem.

Regards,

Gleison

[mats_petersson]

Just to be clear, “What are you actually trying to achieve?” was meant to ask what is your overall goal, and given that overall goal - not the transformation of the IR, but “why do you need to do this” - as a simple performance enhancement, or for some other reason?

And like has been stated, alias-analysis will help here, but some cases, the compiler will not be able to certainly say that no access from the pointer will affect something else, meaning that the compiler NEEDS to take the conservative route and reload the pointer - it doesn’t seem to be a -fstrict-alias flag for clang, like that of gcc.

[Gleison_Souza]

Hi Mats,

so, my overall goal is to insert annotations in the original C
source. I produce these annotations after analyzing the bytecode that
clangs gives me for that source. Thus, I need debugging information in
the bytecode file. What are these annotations? They are comments
relating variables which are pointers and their sizes, as program
symbols. For instance, if I have a program like this one below:

void foo(int *v, int N) {
int i;
for (i = 0; i < N; i++) {
v[i] = 0;
}
}

I insert the following comment on this code:

void foo(int *v, int N) {
int i;
// v is accessed within the loop, and its size is [0…N-1]
for (i = 0; i < N; i++) {
v[i] = 0;
}
}

My prototype infers that ‘v’ is a pointer, and that it ranges on
the region &v + 0 till &v + N - 1, where ‘N’ is a variable alive at
the beginning of the loop. In the end, my analysis works for many
kinds of programs, but I am having problems to infer that ‘v’ is an
array with stable bounds whenever its base pointer (GetElementPtr)
comes out of a load instruction which is inside the loop. That’s way I
would like to be able to hoist out as many loads as I can. The
question then is: what is the command line that I should pass to opt
that is likely to hoist loads outside loops while preserving debugging
info? Mehdi’s suggestion got me really close (clang -O1 -S -o - -mllvm
-print-after-all), but it is removing debugging information away from
the code. Without debugging information, I can’t associate names at
the bytecode level with names at the C-source level.

Regards,

Gleison

[mehdi_amini]

Hi,

Thanks Mehdi,

I tried to use this, but some debug information can be lost in these optimizations.
I need write in the source file to insert information before the loops, and in
some cases, I’m writing after the loop header.

I’m not sure what you mean.

Please, take a look:

int foo1 (int *a, int *b, int n) {
int i, s= 0;
for (i = 0; i < n; i++) {
s = s * a[i];
}

for (i = 0; i < n; i++) {
b[i] = a[i] + 3;
s += a[i];
}
return s;
}

What is the problem with the code generated on this example?
You were asking a specific question related to global variable before, now there is none.

In this case, using the line obtained by this one in the LLVM’s IR:

Line = l->getStartLoc().getLine();

The source file is cloned, and I’m writing my annotations inside the loop now.
I can’t do several modifications in the struct of code, just the necessary, thats the problem.

This is all getting even more confusing to me…

[mehdi_amini]

This doesn’t sounds like a good solution to rely on debug information for that, as you may have figured out.
Have you looked at what Polly is doing do infer such bounds?

Some alternative more robust scheme would be to use pragmas instead of comment and have the front-end parse these pragma and lower the information you want in something like llvm.assume.

[mats_petersson]

I’m a bit confused too. I have no idea how to “know” that v is an array with stable limits in your example. That would highly depend on the call to foo, which you haven’t given in your example - and from a C or C++ perspective, could be just about any pointer to int, from a single int variable having its address taken, to a dynamically allocated result of std::vector<int>::data() - or malloc, new, local variable - including variable length arrays with runtime determined bounds.

Also, I don’t see why the variable being accessed inside or outside the loop will matter? Surely it’s just a matter of determining that it’s a GEP instruction, and understanding what its base is, regardless of where that source is?

My Pascal compiler has (partial) support for range-checking, but I guess this works better in Pascal where arrays always have a fixed size [well, at least in my implementation, which doesn’t have Borland/Turbo Pascal extensions passing the array bounds to the function], and can’t by, for example, dynamically sized.

However, debug symbols should be maintained by LLVM, as long as you use -g, even if some code gets moved around, the original location of that is maintained (in my experience at least, both with debugging clang-generated code and adding debug info to my own compiler).

[Gleison_Souza]

Dear all,

I’m trying to determine the boundaries speculatively.

Some more robust alternative scheme would be to use pragmas instead of comment
and have the front-end parse These pragma and lower the information you want in
something like llvm.assume.

I’m a bit confused too. I have no idea how to “know” that V is an array with stable limits in your example. That would highly depend on the call to foo, Which you have not given in your example - and from a C or C ++ perspective, Could be just about any pointer to int, from a single int variable having its address taken , to a dynamically allocated result of std :: vector <int> :: data () '- or malloc, new`, the local variable - including variable length arrays with runtime determined bounds.

I’m trying to determine the boundaries just analyzing the IR, the tool inserts the
comment of automatic form.

This example, of the one you sent just before (without global variable), does not have a load for the base address in the IR optimized.

Yes, I sent as an example of what I’m doing. Apparently, no optimization is so powerful,
because in some situations, alias occurrence prevents me to estimate the limits, as it can
prevent other tools to estimate the boundaries similarly.

Thanks for help.

Gleison