Page MenuHomePhabricator

[LoopPred] Handle a subset of NE comparison based latches
ClosedPublic

Authored by reames on May 31 2019, 1:45 PM.

Details

Summary

At the moment, LoopPredication completely bails out if it sees a latch of the form:
%cmp = icmp ne %iv, %N
br i1 %cmp, label %loop, label %exit
OR
%cmp = icmp ne %iv.next, %NPlus1
br i1 %cmp, label %loop, label %exit

This is unfortunate since this is exactly the form that LFTR likes to produce. So, go ahead and recognize simple cases where we can.

For pre-increment loops, we leverage the fact that LFTR likes canonical counters (i.e. those starting at zero) and a (presumed) range fact on RHS to discharge the check trivially.

For post-increment forms, the key insight is in remembering that LFTR had to insert a (N+1) for the RHS. CVP can hopefully prove that add nsw/nuw (if there's appropriate range on N to start with). This leaves us both with the post-inc IV and the RHS involving an nsw/nuw add, and SCEV can discharge that with no problem.

This does still need to be extended to handle non-one steps, or other harder patterns of variable (but range restricted) starting values. That'll come later.

Diff Detail

Repository
rL LLVM

Event Timeline

reames created this revision.May 31 2019, 1:45 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 31 2019, 1:45 PM
reames updated this revision to Diff 202494.May 31 2019, 3:22 PM

Rebased on revised tests and remove the public/private hackery

reames edited the summary of this revision. (Show Details)May 31 2019, 3:34 PM
reames updated this revision to Diff 202498.May 31 2019, 3:35 PM

Remove a mistaken comment.

apilipenko accepted this revision.May 31 2019, 5:23 PM
This revision is now accepted and ready to land.May 31 2019, 5:23 PM
This revision was automatically updated to reflect the committed changes.