llvm dev - Dec 2012 - [LLVMdev] Predictive Commoning / Scalar Replacement

On 12/1/2012 7:10 PM, Nick Lewycky wrote:
>
> I don't know of any, but I was wondering if you could point me to the
> paper that describes predictive commoning? I could only find the
> second-order predictive commoning paper, which if I understand correctly
> is a much newer and different algorithm.
I think the original paper was some internal IBM publication.

The idea is basically to reuse values loaded in previous loop iterations.

For example
   for (i) {
     x += 2*t[i-1] - t[i+1];
   }
would become
   for (i) {
     tm1 = tz;     // t-minus-1 = t-zero
     tz  = tp1;    // t-zero    = t-plus-1
     tp1 = t[i+1]; // t-plus-1  = load
     x += 2*tm1 - tp1;
   }

-Krzysztof


-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

On 12/1/2012 7:36 PM, Krzysztof Parzyszek wrote:
>
> I think the original paper was some internal IBM publication.
Here's what I believe to be the reference:

K.O'Brien, B.Hay, J.Minish, H.Schaffer, B.Schloss, A.Shepherd, and 
M.Zaleski, "Advanced compiler technology for the RISC System/6000 
Architecture," IBM RISC System/6000 Technology, SA23-2619, IBM Corp., 
1990, pp. 154-161.


-Krzysztof


-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

There is a non-internal techpub for this somewhere, though it escapes me.
My recollection is that TPO (the middle end of XLC) had moved on to
2nd order predictive quite a while ago.

At least, the implementation I saw 6+ years ago in TPO was much closer
to what is described in the 2nd order paper.


On Sat, Dec 1, 2012 at 8:36 PM, Krzysztof Parzyszek
<kparzysz at codeaurora.org> wrote:
> On 12/1/2012 7:10 PM, Nick Lewycky wrote:
>>
>>
>> I don't know of any, but I was wondering if you could point me to
the
>> paper that describes predictive commoning? I could only find the
>> second-order predictive commoning paper, which if I understand
correctly
>> is a much newer and different algorithm.
>
>
> I think the original paper was some internal IBM publication.
>
> The idea is basically to reuse values loaded in previous loop iterations.
>
> For example
>   for (i) {
>     x += 2*t[i-1] - t[i+1];
>   }
> would become
>   for (i) {
>     tm1 = tz;     // t-minus-1 = t-zero
>     tz  = tp1;    // t-zero    = t-plus-1
>     tp1 = t[i+1]; // t-plus-1  = load
>     x += 2*tm1 - tp1;
>   }
>
> -Krzysztof
>
>
> --
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted
by
> The Linux Foundation
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On 12/1/2012 10:38 PM, Daniel Berlin wrote:
> There is a non-internal techpub for this somewhere, though it escapes me.
> My recollection is that TPO (the middle end of XLC) had moved on to
> 2nd order predictive quite a while ago.
>
> At least, the implementation I saw 6+ years ago in TPO was much closer
> to what is described in the 2nd order paper.
TPO never had any other predictive commoning.  The TPO's implementation 
was written by the guy who wrote the paper (Arie).

-Krzysztof


-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

Hi,

Is predictive commoning implemented in LLVM for now?
what's the status of it?

Regards,
Ilya