[SCEV][ScalarEvolution] SE limitation impacting LV

Hi!

I would appreciate some feedback from someone with experience in SCEV/SE. D39346 tries to fix an issue in LV (PR34965) that exposes a limitation in SCEV/SE. The best solution to the LV issue might not be a fix at SCEV/SE level but we may want to report/address SCEV/SE limitation as well.

For the snippet below, LV expects SE to return a SCEVAddRecExpr for %21. However, SE returns ((4 * (zext i32 (2 + %18) to i64)) + undef), probably because it’s not able to deduce that %bc.resume.val1 = %bc.resume.val + 1. You can find further information in D39346 and the full test in PR34965 (“IR_after_createVectorizedLoopSkeleton” attachment).

I could open a new bug against SCEV/SE if a fix or extension is feasible at that level.

Thanks,

Diego

Hi,

SCEV is fairly conservative around PHI nodes that aren't recurrences
and aren't obviously equivalent to a min-max branch-phi idiom. Is
that the limitation you're running into here?

-- Sanjoy

Thanks for the feedback, Sanjoy.

  > SCEV is fairly conservative around PHI nodes that aren't recurrences and aren't obviously equivalent to a min-max branch-phi idiom. Is that the limitation you're running into here?

Yes, that's exactly the problem. The problematic PHI nodes (%bc.resume.val and %bc.resume.val1) aren't either recurrences or related to min-max idioms. I have a tentative fix for the LV bug and I just wanted to know if this is something that should also be fixed at SCEV level to report a bug accordingly. Your previous comment sounds like "this is a well-known limitation in SCEV" so maybe there is nothing new to report.

Thanks,
Diego

The PHI node %18 is equivalent to a recurrence, so in theory SCEV could analyze it... but it would be complicated to prove that. Specifically, it would have to prove %17 - 1 == %18, which means proving the relationship between %bc.resume.val and %bc.resume.val1. There isn't any code in SCEV to do that sort of analysis.

You probably should fix the vectorizer to avoid generating PHI nodes like %18; even if the vectorizer itself doesn't care if SCEV can analyze the remainder loop, it matters to later passes like LSR.

-Eli

The PHI node %18 is equivalent to a recurrence, so in theory SCEV could
analyze it... but it would be complicated to prove that. Specifically, it
would have to prove %17 - 1 == %18, which means proving the relationship
between %bc.resume.val and %bc.resume.val1. There isn't any code in SCEV to
do that sort of analysis.

+1

        > SCEV is fairly conservative around PHI nodes that aren't
recurrences and aren't obviously equivalent to a min-max branch-phi idiom.
Is that the limitation you're running into here?
  Yes, that's exactly the problem. The problematic PHI nodes
(%bc.resume.val and %bc.resume.val1) aren't either recurrences or related to
min-max idioms. I have a tentative fix for the LV bug and I just wanted to
know if this is something that should also be fixed at SCEV level to report
a bug accordingly. Your previous comment sounds like "this is a well-known
limitation in SCEV" so maybe there is nothing new to report.

Yes.

However, feel free to send patches if there are specific cases you
want SCEV to handle (design-wise a limited amount of ad-hoc logic here
seems fine to me:
https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/ScalarEvolution.cpp#L5072).

-- Sanjoy

Ok. Thanks a lot for the feedback!

You probably should fix the vectorizer to avoid generating PHI nodes like %18;
even if the vectorizer itself doesn't care if SCEV can analyze the remainder loop,
it matters to later passes like LSR.

I agree. As Ayal and Gil mentioned in D39346, even the vectorizer might care if SCEV can't analyze the remainder loop if we eventually want to vectorize it.
I'll report this issue.

Thanks,
Diego