Loop Metadata?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Loop Metadata?

Hal Finkel
Is there currently a good way of attaching metadata to loops?

The use case that I have in mind is implementing a feature whereby the
user can put
#pragma unroll(N)
above a loop and that serves has an instruction to the optimizer to
unroll the loop N times.

I understand that LLVM does not have a first-class loop construct, but
would attaching the metadata to the instructions that branch to the loop
header be a good idea?

I also wonder whether whatever mechanism would work for this purpose
would also work for implementing OpenMP support.

Thanks again,
Hal

--
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Loop Metadata?

Devang Patel

On Feb 10, 2012, at 10:19 AM, Hal Finkel <[hidden email]> wrote:

> Is there currently a good way of attaching metadata to loops?
>
> The use case that I have in mind is implementing a feature whereby the
> user can put
> #pragma unroll(N)
> above a loop and that serves has an instruction to the optimizer to
> unroll the loop N times.
>
> I understand that LLVM does not have a first-class loop construct, but
> would attaching the metadata to the instructions that branch to the loop
> header be a good idea?

That's the starting point. The key is how to chose loop identifying instruction (or instructions ?) for the annotation and preserve the annotation through transformations. At some point during optimization, it may be a good idea to hand it over to LoopPassManager.

-
Devang

> I also wonder whether whatever mechanism would work for this purpose
> would also work for implementing OpenMP support.
>
> Thanks again,
> Hal
>
> --
> Hal Finkel
> Postdoctoral Appointee
> Leadership Computing Facility
> Argonne National Laboratory
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Loop Metadata?

Sebastian Pop-7
On Fri, Feb 10, 2012 at 1:14 PM, Devang Patel <[hidden email]> wrote:

>
> On Feb 10, 2012, at 10:19 AM, Hal Finkel <[hidden email]> wrote:
>
>> Is there currently a good way of attaching metadata to loops?
>>
>> The use case that I have in mind is implementing a feature whereby the
>> user can put
>> #pragma unroll(N)
>> above a loop and that serves has an instruction to the optimizer to
>> unroll the loop N times.

I had something similar in mind for #pragma vectorize

>> I understand that LLVM does not have a first-class loop construct, but
>> would attaching the metadata to the instructions that branch to the loop
>> header be a good idea?
>
> That's the starting point. The key is how to chose loop identifying instruction (or instructions ?) for the annotation and preserve the annotation through transformations. At some point during optimization, it may be a good idea to hand it over to LoopPassManager.
>

I don't think annotations are good to implement pragmas.
Annotations are going to disappear if you dump the code to file.
Pragma are a hard contract in between the programmer and the
compiler: the compiler cannot afford loosing a pragma information.

I was considering something like using a builtin call to transmit
the pragma info from the front-end throughout the compiler.
That would expose the pragma "call" in the IR and LLVM would
have to deal with it as a first class construct.
This would avoid loosing the pragma annotation on the way.

Speaking about OpenMP, I think that a big part of it should be
taken care of in the clang front-end.  I do not think that we should
expose syntactic kind of info to the middle-end optimizers.

Sebastian
--
Qualcomm Innovation Center, Inc is a member of Code Aurora Forum

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Loop Metadata?

Devang Patel

On Feb 10, 2012, at 1:42 PM, Sebastian Pop <[hidden email]> wrote:

> On Fri, Feb 10, 2012 at 1:14 PM, Devang Patel <[hidden email]> wrote:
>>
>> On Feb 10, 2012, at 10:19 AM, Hal Finkel <[hidden email]> wrote:
>>
>>> Is there currently a good way of attaching metadata to loops?
>>>
>>> The use case that I have in mind is implementing a feature whereby the
>>> user can put
>>> #pragma unroll(N)
>>> above a loop and that serves has an instruction to the optimizer to
>>> unroll the loop N times.
>
> I had something similar in mind for #pragma vectorize
>
>>> I understand that LLVM does not have a first-class loop construct, but
>>> would attaching the metadata to the instructions that branch to the loop
>>> header be a good idea?
>>
>> That's the starting point. The key is how to chose loop identifying instruction (or instructions ?) for the annotation and preserve the annotation through transformations. At some point during optimization, it may be a good idea to hand it over to LoopPassManager.
>>
>
> I don't think annotations are good to implement pragmas.
> Annotations are going to disappear if you dump the code to file.
> Pragma are a hard contract in between the programmer and the
> compiler: the compiler cannot afford loosing a pragma information.
>
> I was considering something like using a builtin call to transmit
> the pragma info from the front-end throughout the compiler.
> That would expose the pragma "call" in the IR and LLVM would
> have to deal with it as a first class construct.
> This would avoid loosing the pragma annotation on the way.

How would you tie a built-in call with a loop ?

>
> Speaking about OpenMP, I think that a big part of it should be
> taken care of in the clang front-end.  I do not think that we should
> expose syntactic kind of info to the middle-end optimizers.
>
> Sebastian
> --
> Qualcomm Innovation Center, Inc is a member of Code Aurora Forum

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Loop Metadata?

Sebastian Pop-7
On Fri, Feb 10, 2012 at 3:53 PM, Devang Patel <[hidden email]> wrote:
> How would you tie a built-in call with a loop ?

The same way as Hal was saying: tag the loop header.

Sebastian
--
Qualcomm Innovation Center, Inc is a member of Code Aurora Forum
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Loop Metadata?

Tobias Grosser-5
On 02/10/2012 11:29 PM, Sebastian Pop wrote:
> On Fri, Feb 10, 2012 at 3:53 PM, Devang Patel<[hidden email]>  wrote:
>> How would you tie a built-in call with a loop ?
>
> The same way as Hal was saying: tag the loop header.

So how do we tag the loop header? ;-)

If we just put the instruction in the header, in the worst case LICM
will move it to header basic block of another loop. :-(

We could try to keep it somehow attached to the loop. E.g. by making it
modify a scalar that is changed in each loop iteration. But than again,
some sophisticated loop fission pass may move these instructions apart.
We definitely need some conventions for such an approach. Another issue
is, that as more semantics we put into such a loop marking instruction,
the more probable it is that we block optimizations like dead code
elimination of the entire loop. If we do not put any semantics, we may
risk to loose the annotation.

Another option that I see is somehow in the direction of what Devang
pointed out. We could make our intention of maintain information about
the loops more explicit. I could e.g. imagine having some permanent
pass/analysis, maybe called LoopInformationManager, that is in charge of
the loop meta data. When reading LLVM-IR it initializes itself by
reading the loop meta-data. Other passes can call the
LoopInformationManager for the information they are interested in.
Passes that do not touch the loop structure need to explicitly specify
that they preserved the loop semantics. In case this is not done, the
LoopInformationManager removes the meta-data from the loop. Or in case
it is informed about a change, it adapts the meta-data accordingly. Such
that at the end, only valid meta-data will be written out.
This approach has its own drawbacks, but it may be a direction we could
consider.

Cheers
Tobi

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Loop Metadata?

Sebastian Pop-7
On Sat, Feb 11, 2012 at 10:17 AM, Tobias Grosser <[hidden email]> wrote:

> On 02/10/2012 11:29 PM, Sebastian Pop wrote:
>> On Fri, Feb 10, 2012 at 3:53 PM, Devang Patel<[hidden email]>  wrote:
>>> How would you tie a built-in call with a loop ?
>>
>> The same way as Hal was saying: tag the loop header.
>
> So how do we tag the loop header? ;-)
>
> If we just put the instruction in the header, in the worst case LICM
> will move it to header basic block of another loop. :-(

I don't think that optimizers are going to touch a builtin call for which
they don't understand the side effects.  If they do, then they will get
what they deserve: bug reports.

> We could try to keep it somehow attached to the loop. E.g. by making it
> modify a scalar that is changed in each loop iteration. But than again,
> some sophisticated loop fission pass may move these instructions apart.
> We definitely need some conventions for such an approach. Another issue
> is, that as more semantics we put into such a loop marking instruction,
> the more probable it is that we block optimizations like dead code
> elimination of the entire loop. If we do not put any semantics, we may
> risk to loose the annotation.
>
> Another option that I see is somehow in the direction of what Devang
> pointed out. We could make our intention of maintain information about
> the loops more explicit. I could e.g. imagine having some permanent
> pass/analysis, maybe called LoopInformationManager, that is in charge of
> the loop meta data. When reading LLVM-IR it initializes itself by
> reading the loop meta-data. Other passes can call the
> LoopInformationManager for the information they are interested in.
> Passes that do not touch the loop structure need to explicitly specify
> that they preserved the loop semantics. In case this is not done, the
> LoopInformationManager removes the meta-data from the loop. Or in case
> it is informed about a change, it adapts the meta-data accordingly. Such
> that at the end, only valid meta-data will be written out.
> This approach has its own drawbacks, but it may be a direction we could
> consider.

I think that storing information on the side is good for the results of a
program analysis that can be recomputed if the information is lost.
On the other hand, the information that the programmer has put in a
pragma cannot be recomputed, and so in my opinion that should be
part of the IR.

Sebastian
--
Qualcomm Innovation Center, Inc is a member of Code Aurora Forum

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev