Predictive Commoning / Scalar Replacement

Project Infrastructure LLVM Dev List Archives
#1

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

#2

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

#3

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

#4

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

#5

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.

#6

TPO never had any other predictive commoning. The TPO's implementation was written by the guy who wrote the paper (Arie).

-Krzysztof

#7

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

#8

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

#9

Hi,

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

Regards,
Ilya