New Loop Versioning LICM Pass

Description

New Loop Versioning LICM Pass

Summary:
When alias analysis is uncertain about the aliasing between any two accesses,
it will return MayAlias. This uncertainty from alias analysis restricts LICM
from proceeding further. In cases where alias analysis is uncertain we might
use loop versioning as an alternative.

Loop Versioning will create a version of the loop with aggressive aliasing
assumptions in addition to the original with conservative (default) aliasing
assumptions. The version of the loop making aggressive aliasing assumptions
will have all the memory accesses marked as no-alias. These two versions of
loop will be preceded by a memory runtime check. This runtime check consists
of bound checks for all unique memory accessed in loop, and it ensures the
lack of memory aliasing. The result of the runtime check determines which of
the loop versions is executed: If the runtime check detects any memory
aliasing, then the original loop is executed. Otherwise, the version with
aggressive aliasing assumptions is used.

The pass is off by default and can be enabled with command line option
-enable-loop-versioning-licm.

Reviewers: hfinkel, anemet, chatur01, reames

Subscribers: MatzeB, grosser, joker.eph, sanjoy, javed.absar, sbaranga,

llvm-commits

Differential Revision: http://reviews.llvm.org/D9151

Details

Committed
AshutoshFeb 5 2016, 11:47 PM
Differential Revision
D9151: Loop Versioning for LICM
Parents
rL259985: Re-apply r259977 - [OpenMP] Reorganize code to allow specialized code…
Branches
Unknown
Tags
Unknown

Just found this linked to from llvm weekly, and was wondering whether this works on the testcase in PR11331 and the dupes of that bug.

/llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp
382

Typo, "inining" -> "inlining"

383–385

It could also have the opposite effect. Suppose the inliner knows the noalias/mustalias of two function arguments and uses that knowledge to pick which of the two function versions will actually run, and the other version is marked as zero-cost. If the version of the loop that the inliner sees will run is smaller than the pre-LICM loop, it may permet inlining in cases we would've otherwise thought the function is too large.

/llvm/trunk/lib/Transforms/Scalar/LoopVersioningLICM.cpp
52

Extra | in "Orig Loop|Exit Block".

95

Please make this a static constexpr (string or char[]).

102

I'm surprised this works; the option name should not include the leading hyphen.

109

Again here.

375

Don't use dyn_cast and discard the result, use isa<> instead.

430

"in unsafe" -> "is unsafe"

472

Capitalization?

Thanks Nick, I will incorporate your comments.

/llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp
383–385

Scheduled at this place based on the general assumption that inlining will help with
better aliasing decision. Also if we schedule this pre-inlining the clone loop and
the runtime check can make function too large, might result in a valid inline candidate
not getting inlined.