Caballero, Diego via llvm-dev
2017-Nov-22 23:43 UTC
[llvm-dev] [SCEV][ScalarEvolution] SE limitation impacting LV
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 -----Original Message----- From: Sanjoy Das [mailto:sanjoy at playingwithpointers.com] Sent: Wednesday, November 22, 2017 2:58 PM To: Caballero, Diego <diego.caballero at intel.com> Cc: llvm-dev at lists.llvm.org Subject: Re: [llvm-dev] [SCEV][ScalarEvolution] SE limitation impacting LV 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 On Tue, Nov 14, 2017 at 9:16 AM, Caballero, Diego via llvm-dev <llvm-dev at lists.llvm.org> wrote:> 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))<nuw><nsw> + > undef)<nsw>, 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 > > > > ---- > > > > .outer: ; preds = %2, %0 > > … > > %.ph2 = phi i32 [ 62, %2 ], [ 110, %0 ] > > %5 = add i32 %.ph2, 1 > > … > > > > vector.ph: ; preds = %.outer > > … > > %ind.end = add i32 %5, %n.vec > > %ind.end2 = add i32 %.ph2, %n.vec > > … > > > > middle.block: ; preds > %vector.body.latch > > … > > > > scalar.ph: ; preds = %middle.block, > %.outer > > %bc.resume.val = phi i32 [ %ind.end, %middle.block ], [ %5, %.outer > ] > > %bc.resume.val1 = phi i32 [ %ind.end2, %middle.block ], [ %.ph2, > %.outer ] > > br label %16 > > > > ; <label>:16: ; preds = %16, %scalar.ph > > %17 = phi i32 [ %bc.resume.val, %scalar.ph ], [ %23, %16 ] > > %18 = phi i32 [ %bc.resume.val1, %scalar.ph ], [ %17, %16 ] > > %19 = add i32 %18, 2 > > %20 = zext i32 %19 to i64 > > %21 = getelementptr inbounds i32, i32 addrspace(1)* undef, i64 %20 > > %22 = ashr i32 undef, %4 > > store i32 %22, i32 addrspace(1)* %21, align 4 > > %23 = add i32 %17, 1 > > %24 = icmp sgt i32 %23, 61 > > br i1 %24, label %._crit_edge.loopexit.preheader, label %16 > > > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >
Friedman, Eli via llvm-dev
2017-Nov-23 00:23 UTC
[llvm-dev] [SCEV][ScalarEvolution] SE limitation impacting LV
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 On 11/22/2017 3:43 PM, Caballero, Diego via llvm-dev wrote:> 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 > > -----Original Message----- > From: Sanjoy Das [mailto:sanjoy at playingwithpointers.com] > Sent: Wednesday, November 22, 2017 2:58 PM > To: Caballero, Diego <diego.caballero at intel.com> > Cc: llvm-dev at lists.llvm.org > Subject: Re: [llvm-dev] [SCEV][ScalarEvolution] SE limitation impacting LV > > 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 > > On Tue, Nov 14, 2017 at 9:16 AM, Caballero, Diego via llvm-dev <llvm-dev at lists.llvm.org> wrote: >> 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))<nuw><nsw> + >> undef)<nsw>, 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 >> >> >> >> ---- >> >> >> >> .outer: ; preds = %2, %0 >> >> … >> >> %.ph2 = phi i32 [ 62, %2 ], [ 110, %0 ] >> >> %5 = add i32 %.ph2, 1 >> >> … >> >> >> >> vector.ph: ; preds = %.outer >> >> … >> >> %ind.end = add i32 %5, %n.vec >> >> %ind.end2 = add i32 %.ph2, %n.vec >> >> … >> >> >> >> middle.block: ; preds >> %vector.body.latch >> >> … >> >> >> >> scalar.ph: ; preds = %middle.block, >> %.outer >> >> %bc.resume.val = phi i32 [ %ind.end, %middle.block ], [ %5, %.outer >> ] >> >> %bc.resume.val1 = phi i32 [ %ind.end2, %middle.block ], [ %.ph2, >> %.outer ] >> >> br label %16 >> >> >> >> ; <label>:16: ; preds = %16, %scalar.ph >> >> %17 = phi i32 [ %bc.resume.val, %scalar.ph ], [ %23, %16 ] >> >> %18 = phi i32 [ %bc.resume.val1, %scalar.ph ], [ %17, %16 ] >> >> %19 = add i32 %18, 2 >> >> %20 = zext i32 %19 to i64 >> >> %21 = getelementptr inbounds i32, i32 addrspace(1)* undef, i64 %20 >> >> %22 = ashr i32 undef, %4 >> >> store i32 %22, i32 addrspace(1)* %21, align 4 >> >> %23 = add i32 %17, 1 >> >> %24 = icmp sgt i32 %23, 61 >> >> br i1 %24, label %._crit_edge.loopexit.preheader, label %16 >> >> >> >> >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >> > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-- Employee of Qualcomm Innovation Center, Inc. Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project
Sanjoy Das via llvm-dev
2017-Nov-23 20:03 UTC
[llvm-dev] [SCEV][ScalarEvolution] SE limitation impacting LV
On Wed, Nov 22, 2017 at 4:23 PM, Friedman, Eli <efriedma at codeaurora.org> wrote:> 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