[llvm-dev] Generalizing load/store promotion in LICM

[Krzysztof Parzyszek via llvm-dev]

On 9/12/2018 4:41 PM, Philip Reames via llvm-dev wrote:
> 
> Proposal A - Use predicated stores in loop exits
> 
> The basic idea is that we don't worry about solving the legality 
> question above, and just insert a store which is predicated on a 
> condition which is true exactly when the original store ran.  In pseudo 
> code, this looks something like:
> 
> bool StoreLegal = false;
> int LocalCount = g_count;
> for (int = 0; i < N; i++)
>    if (a[i] == 0) {
>      LocalCount++;
>      StoreLegal = true;
>    }
> if (StoreLegal) g_count = LocalCount;
> 
> There are two obvious concerns here:
> 
>  1. The predicated store might be expensive in practice - true for most
>     current architectures.
>  2. We''re introducing an extra boolean phi cycle around the loop.

In many practical scenarios you can write to g_count unconditionally, so 
if that's the case, then the tracking of store's occurrence could be 
omitted. If N is large enough, the amortized cost of that store would be 
very small.
There should be some mechanism to convey this kind of information, since 
it could be difficult to determine it by simply examining the function.


> Proposal B - Separate load and store handling into distinct transforms
> 
> (For folks I've discussed this with before, this part is all new.)
> 
> Thinking about the problem, it finally occurred to me that we can 
> decompose the original example into two steps: getting the loads out of 
> the loop, and sinking the stores out of the loop.  If we can accomplish 
> the former, but not the later, we've still made meaningful progress.
> 
> So, what'd we'd essentially have is a load only transformation which 
> produces this:
> int LocalCount = g_count;
> for (int = 0; i < N; i++)
>    if (a[i] == 0) {
>      LocalCount++;
>      g_count = LocalCount;
>    }

The stores to g_count could be considered "redundant", since the value 
in g_count is always the same as the value in LocalCount. In that sense, 
moving the store out of the loop would be a form of PRE. This could also 
introduce predication to the store if necessary.

-Krzysztof


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