HomePhabricator

[Guards] Introduce loop-predication pass

Description

[Guards] Introduce loop-predication pass

This patch introduces guard based loop predication optimization. The new LoopPredication pass tries to convert loop variant range checks to loop invariant by widening checks across loop iterations. For example, it will convert

for (i = 0; i < n; i++) {
  guard(i < len);
  ...
}

to

for (i = 0; i < n; i++) {
  guard(n - 1 < len);
  ...
}

After this transformation the condition of the guard is loop invariant, so loop-unswitch can later unswitch the loop by this condition which basically predicates the loop by the widened condition:

if (n - 1 < len)
  for (i = 0; i < n; i++) {
    ...
  } 
else
  deoptimize

This patch relies on an NFC change to make ScalarEvolution::isMonotonicPredicate public (revision 293062).

Reviewed By: sanjoy

Differential Revision: https://reviews.llvm.org/D29034

Details

Committed
apilipenkoJan 25 2017, 8:00 AM
Reviewer
sanjoy
Differential Revision
D29034: [Guards] Introduce loop-predication pass
Parents
rL293063: [AArch64] Minor code refactoring. NFC.
Branches
Unknown
Tags
Unknown