llvm dev - Feb 2016 - Particular type of loop optimization

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>

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.

--
Mats

On 3 February 2016 at 12:05, Gleison Souza via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> 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
>>
>>
>>
>
> _______________________________________________
> 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/20160203/cfeb3250/attachment.html>

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

2016-02-03 11:06 GMT-02:00 mats petersson <mats at planetcatfish.com>:
> 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.
>
> --
> Mats
>
> On 3 February 2016 at 12:05, Gleison Souza via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> 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
>>>
>>>
>>>
>>
>> _______________________________________________
>> 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/20160203/4b75688d/attachment.html>

Hi,

> On Feb 3, 2016, at 4:05 AM, Gleison Souza <gleison14051994 at
gmail.com> wrote:
> 
> 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


> 
> Regards,
> 
>     Gleison
> 
> 2016-02-03 1:07 GMT-02:00 Mehdi Amini <mehdi.amini at apple.com
<mailto:mehdi.amini at apple.com>>:
> 
>> On Feb 2, 2016, at 8:35 AM, Gleison Souza via llvm-dev <llvm-dev at
lists.llvm.org <mailto: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/aceac498/attachment.html>