Page MenuHomePhabricator

[LoopUnroll] Keep the loop test only on the first iteration of max-or-zero loops
ClosedPublic

Authored by john.brawn on Oct 17 2016, 9:09 AM.

Details

Summary

When we have a loop with a known upper bound on the number of iterations, and furthermore know that either the number of iterations will be either exactly that upper bound or zero, then we can fully unroll up to that upper bound keeping only the first loop test to check for the zero iteration case.

Most of the work here is in plumbing this 'max-or-zero' information from the part of scalar evolution where it's detected through to loop unrolling. I've also gone for the safe default of 'false' everywhere but howManyLessThans which could probably be improved.

Diff Detail

Repository
rL LLVM

Event Timeline

john.brawn updated this revision to Diff 74857.Oct 17 2016, 9:09 AM
john.brawn retitled this revision from to [LoopUnroll] Keep the loop test only on the first iteration of max-or-zero loops.
john.brawn updated this object.
john.brawn set the repository for this revision to rL LLVM.
john.brawn added a subscriber: llvm-commits.
jmolloy added a subscriber: jmolloy.

The LoopUnroll changes look very reasonable to me, but I'd like Silviu's opinion on the SCEV plumbing.

haicheng edited edge metadata.Oct 19 2016, 10:49 AM

The loop unrolling part looks good to me, too. I am not an expert of SCEV.

include/llvm/Transforms/Utils/UnrollLoop.h
35 ↗(On Diff #74857)

Thank you for catching my mistake.

sbaranga added inline comments.
include/llvm/Analysis/ScalarEvolution.h
1394 ↗(On Diff #74857)

I've only taken a brief look at this, but it might be a nicer interface to add a getMaxOrZeroBackedgeTakenCount. That way we don't have to add the MaxOrZero everywhere (same in other places) and would look more like the existing code.

lib/Analysis/ScalarEvolution.cpp
5741 ↗(On Diff #74857)

Does this work with more than one loop exit and with predicated loop exits?

I'm not certain this would hold if we have at least one loop exit that doesn't dominate the latch, given the very strict definition (the backedge gets taken exactly 0 or MaxNotTaken times).

john.brawn added inline comments.Oct 20 2016, 3:26 AM
lib/Analysis/ScalarEvolution.cpp
5741 ↗(On Diff #74857)

That's handled down on line 5759 - MaxOrZero is set to false on loops with more than one exit.

sbaranga added inline comments.Oct 20 2016, 6:50 AM
lib/Analysis/ScalarEvolution.cpp
5741 ↗(On Diff #74857)

Good point, I've missed that. It should be fine then.

john.brawn updated this revision to Diff 75295.Oct 20 2016, 7:13 AM
john.brawn edited edge metadata.

Pass the MaxOrZero information through to loop unrolling using a separate function instead of via a pointer argument.

LGTM for the SCEV part.

This revision was automatically updated to reflect the committed changes.