[LLVMdev] LICM and SCEV AA?

[Hal Finkel]

Hello,

We currently generate suboptimal code for this loop:

for (int i = 1; i < LEN; i++) {
  a[i] = a[0] + b[i];
}

The largest problem is that we won't vectorize the loop because the loop vectorizer does not grok the independence of a[i] and a[0] (note that i starts at 1 in this loop). While we can probably fix the vectorizer to handle this, I don't think that is the right place for the fix, because this is really a LICM problem. LICM could move a[0] out of the loop, but it currently doesn't (which is pretty suboptimial in itself). The reason is that LICM does not use SE (either directly or indirectly), and BasicAA does not recognize that a[0] and a[i] will never overlap in this loop.

I see several possible solutions:

 1. Add yet-another hack to BasicAA to catch this case.

 2. Let LICM use SE directly. Instead of bailing out on hoisting a loop-invariant value in an alias set with non-invariant values, use SE to check independence with the other values in the alias set.

 3. Use ScalarEvolutionAliasAnalysis; scheduling SCEV AA prior to running LICM fixes this problem.

Using #3 seems like the simplest, and most natural, way to fix this issue. I recall someone tell me (maybe at the developers' meeting) that SCEV AA was 'fundamentally flawed', and now I'm wondering what was meant by that. The pass manager does not know how to reschedule it unless it is specifically requested, but if that's the entirety of the problem, then I think that we could manually schedule it in a few key places and get a lot of benefit (there is a particular use case for prior to LICM, at least).

FWIW, I don't think that adding an SCEV dependency before LICM would be particularly problematic: Currently, LICM lives in the same loop pass manager instance as LoopSimplify, LoopRotate and LoopUnswitch, all of which preserve SE.

Suggestions?

Thanks again,
Hal

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory