Predictive Commoning / Scalar Replacement

Hello,

It seems there is the no redundancy elimination over loop iterations, such

as predictive communing or scalar replacement in LLVM. They are quite usefully

for computation code. I am wondering if any party is working or has plan to

implement those optimizations?

Thanks,

Yin

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

Yin Ma wrote:

Hello,

It seems there is the no redundancy elimination over loop iterations, such

as predictive communing or scalar replacement in LLVM. They are quite
usefully

for computation code. I am wondering if any party is working or has plan to

implement those optimizations?

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.

Nick

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

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

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

To be clear, you are saying TPO's implementation was always 2nd order?
If so, that would make sense :slight_smile:

Sort of. If I remember correctly, the first working implementation might have been simpler, but the final version came shortly thereafter. For all intents and purposes, I consider it to have been implemented in one shot. Look it up in CMVC if you want all the gory details... :wink:

-Krzysztof

Hi,

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

Regards,
Ilya