Page MenuHomePhabricator

Extend peeling to help invariant motion
Needs RevisionPublic

Authored by evstupac on Mar 21 2018, 5:52 PM.

Details

Summary

Apply peeling for loops like:
for (i = 0; i < n; i++) {

if (i >= *a_bound) assert(0); 
s += a[i]; 
if (i >= *b_bound) assert(0); 
s += b[i];

}

Here load *a_bound is safe to speculate and it should be hoisted out of the loop,
However, *b_bound is not safe to speculate, because this will potentially change program behavior:
If we load "b_bound" before the loop and "b_bound" is null we throw an exception, which is wrong if we exit at "i >= *a_bound".
After peeling *b_bound is safe to speculate and hoist it out of the loop (because if it is null - we throw an exception before the loop):

if (0 >= *a_bound) assert(0);
s += a[0];
if (0 >= *b_bound) assert(0);
s += b[0];

for (i = 1; i < n; i++) {

if (i >= *a_bound) assert(0); 
s += a[i]; 
if (i >= *b_bound) assert(0); 
s += b[i];

}

Diff Detail

Repository
rL LLVM

Event Timeline

evstupac created this revision.Mar 21 2018, 5:52 PM
efriedma added inline comments.Mar 21 2018, 6:15 PM
lib/Transforms/Utils/LoopUnrollPeel.cpp
266

This heuristic is a bit suspicious. I'm not sure we always run LICM immediately before unrolling. And even if we do, peeling won't help in a lot of situations; a load could alias another memory operation, or it might not dominate the loop latch.

531

This is really hacky.

There really isn't any reason we can't peel loops with multiple exits; it just isn't implemented yet. Please fix it properly.

evstupac added inline comments.Mar 21 2018, 6:59 PM
lib/Transforms/Utils/LoopUnrollPeel.cpp
266

This is not only about a load. Division also counts.

I'm not sure we always run LICM immediately before unrolling.

It is enough to run it somewhere after unroll/peel.

a load could alias another memory operation

We should be able to hoist out Invariant loads in most cases. At least breaking a dependency is always good. And peeling should not hurt here.

it might not dominate the loop latch

true. There should be a check on this.

531

Well. I agree that putting these methods to LoopAnalysis is not good.
But this is as "hacky" as previous implementation limited to loops with one exit from latch.
The reason I limit peeling to just unreachable exits case is that these exits have close to 0 frequency. For other multiexit loops it is harder to estimate profitability.

However you are right and peeling of multiexit loops is doable and (if you feel this could be profitable) I can create a separate patch for this.

efriedma added inline comments.Mar 21 2018, 7:14 PM
lib/Transforms/Utils/LoopUnrollPeel.cpp
531

If it isn't profitable to unroll multi-exit loops which have more than one likely exit, we can add a check to computePeelCount, rather than canPeel.

mkazantsev requested changes to this revision.Mar 25 2018, 10:26 PM
mkazantsev added inline comments.
lib/Analysis/LoopInfo.cpp
439

This will break semantics of this method in case if this block is exit/unreachable/etc.

452

Braces not needed.

464

Same, you should also check this block on being exit/unreachable.

lib/Transforms/Utils/LoopUnrollPeel.cpp
240

Uninitialized variable will cause UB on line 250.

242

Braces not needed.

254

I think isGuaranteedToTransferExecutionToSuccessor is what you actually need here.

637

Could be const PHINode &PHI : EB->phis()

This revision now requires changes to proceed.Mar 25 2018, 10:26 PM