[llvm-dev] Particular type of loop optimization

Gleison Souza via llvm-dev llvm-dev at lists.llvm.org
Wed Feb 3 12:31:53 PST 2016


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>


More information about the llvm-dev mailing list