llvm dev - Feb 2016 - Particular type of loop optimization

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160202/a0b79a7e/attachment.html>

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)

--
Mats

On 2 February 2016 at 16:35, Gleison Souza via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> 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
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160202/f3b7dbf0/attachment.html>

Do you have alias analysis enabled?

Marcello
> On 2 Feb 2016, at 08:35, Gleison Souza via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> 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
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160202/bd9614bd/attachment.html>

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

2016-02-02 17:10 GMT-02:00 Gleison Souza <gleison14051994 at gmail.com>:
> 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
>
> 2016-02-02 15:59 GMT-02:00 Caldarale, Charles R <
> Chuck.Caldarale at unisys.com>:
>
>> > From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org]
>> > On Behalf Of mats petersson via llvm-dev
>> > Subject: Re: [llvm-dev] Particular type of loop optimization
>>
>> > 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].
>>
>> Such an optimization cannot be made unless the compiler knows that the
>> area spanned by the accesses through vectorE does not include the
location
>> of vectorE itself.  Some TBAA information added to the IR-level loads
and
>> stores should allow that.
>>
>>  - Chuck
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160202/dc9ff887/attachment.html>

> On Feb 2, 2016, at 8:35 AM, Gleison Souza via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> 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;
> }

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

— 
Mehdi


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160202/72c6adb6/attachment.html>

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

2016-02-03 1:07 GMT-02:00 Mehdi Amini <mehdi.amini at apple.com>:
>
> On Feb 2, 2016, at 8:35 AM, Gleison Souza via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> 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;
> }
>
>
>
> 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
>
> —
> Mehdi
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160203/fcd7ac2b/attachment.html>