llvm dev - May 2020 - Question about the order of predecessors in LoopVectorizer with VPlanNatviePath

Hi All,

I have got one domination error after running LoopVectorizer with
VPlanNatviePath.

Let's see simple IR snippet after loop vectorization with VPlanNatviePath.

vector.body:
...
  br label %for.body10.preheader67

for.body10.preheader67:                     ; preds %for.cond.cleanup972,
%vector.body
  %vec.phi = phi <4 x i64> [ zeroinitializer, %for.cond.cleanup972 ],
[ %8, %vector.body ]
...

for.cond.cleanup972:                              ; preds = %for.body1068
  %8 = add nuw nsw <4 x i64> %vec.phi, <i64 1, i64 1, i64 1, i64 1>
...
  br i1 %10, label %for.cond.cleanup373, label %for.body10.preheader67

As you can see, %vec.phi has wrong incoming basic blocks. It could be as below.

%vec.phi = phi <4 x i64> [ %8, %for.cond.cleanup972 ], [
zeroinitializer, %vector.body ]

The problem comes from "InnerLoopVectorizer::fixNonInductionPHIs()".
This function has assumption about the order of predecessors as below.

    // The predecessor order is preserved and we can rely on mapping between
    // scalar and vector block predecessors.
    for (unsigned i = 0; i < NumIncomingValues; ++i) {

It seems it assumes loop latch as first predecessor and loop preheader
as second one or something like that.

I am not sure there is rule to keep the order of predecessors but I
can see Jump Threading pass generates different order of predecessors
on basic blocks.

If llvm does not have the rule about the order of predecessors, it
seems VPlanNatviePath need to consider the different order of
predecessors. How do you think about it?

Thanks
JinGu Kang

Hi,
> On May 17, 2020, at 13:04, jingu kang via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi All,
> 
> I have got one domination error after running LoopVectorizer with
> VPlanNatviePath.
> 
> Let's see simple IR snippet after loop vectorization with
VPlanNatviePath.
> 
> vector.body:
> ...
>  br label %for.body10.preheader67
> 
> for.body10.preheader67:                     ; preds >
%for.cond.cleanup972, %vector.body
>  %vec.phi = phi <4 x i64> [ zeroinitializer, %for.cond.cleanup972 ],
> [ %8, %vector.body ]
> ...
> 
> for.cond.cleanup972:                              ; preds = %for.body1068
>  %8 = add nuw nsw <4 x i64> %vec.phi, <i64 1, i64 1, i64 1, i64
1>
> ...
>  br i1 %10, label %for.cond.cleanup373, label %for.body10.preheader67
> 
> As you can see, %vec.phi has wrong incoming basic blocks. It could be as
below.
> 
> %vec.phi = phi <4 x i64> [ %8, %for.cond.cleanup972 ], [
> zeroinitializer, %vector.body ]
> 
> The problem comes from
"InnerLoopVectorizer::fixNonInductionPHIs()".
> This function has assumption about the order of predecessors as below.
> 
>    // The predecessor order is preserved and we can rely on mapping between
>    // scalar and vector block predecessors.
>    for (unsigned i = 0; i < NumIncomingValues; ++i) {
> 
> It seems it assumes loop latch as first predecessor and loop preheader
> as second one or something like that.
> 
> I am not sure there is rule to keep the order of predecessors but I
> can see Jump Threading pass generates different order of predecessors
> on basic blocks.
> 
> If llvm does not have the rule about the order of predecessors, it
> seems VPlanNatviePath need to consider the different order of
> predecessors. How do you think about it?

Yes that seems like a bug. Could you create a bug repot at https://bugs.llvm.org
or share the reproducer here, if you don’t have an account?

Cheers,
Florian

Hi Florian

Thanks for reply.

I have created a bug https://bugs.llvm.org/show_bug.cgi?id=45958 and a
review https://reviews.llvm.org/D80086
Please review them.

Thanks
JinGu Kang

2020년 5월 17일 (일) 오후 1:51, Florian Hahn <florian_hahn at apple.com>님이
작성:
>
> Hi,
>
> > On May 17, 2020, at 13:04, jingu kang via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> >
> > Hi All,
> >
> > I have got one domination error after running LoopVectorizer with
> > VPlanNatviePath.
> >
> > Let's see simple IR snippet after loop vectorization with
VPlanNatviePath.
> >
> > vector.body:
> > ...
> >  br label %for.body10.preheader67
> >
> > for.body10.preheader67:                     ; preds > >
%for.cond.cleanup972, %vector.body
> >  %vec.phi = phi <4 x i64> [ zeroinitializer,
%for.cond.cleanup972 ],
> > [ %8, %vector.body ]
> > ...
> >
> > for.cond.cleanup972:                              ; preds =
%for.body1068
> >  %8 = add nuw nsw <4 x i64> %vec.phi, <i64 1, i64 1, i64 1,
i64 1>
> > ...
> >  br i1 %10, label %for.cond.cleanup373, label %for.body10.preheader67
> >
> > As you can see, %vec.phi has wrong incoming basic blocks. It could be
as below.
> >
> > %vec.phi = phi <4 x i64> [ %8, %for.cond.cleanup972 ], [
> > zeroinitializer, %vector.body ]
> >
> > The problem comes from
"InnerLoopVectorizer::fixNonInductionPHIs()".
> > This function has assumption about the order of predecessors as below.
> >
> >    // The predecessor order is preserved and we can rely on mapping
between
> >    // scalar and vector block predecessors.
> >    for (unsigned i = 0; i < NumIncomingValues; ++i) {
> >
> > It seems it assumes loop latch as first predecessor and loop preheader
> > as second one or something like that.
> >
> > I am not sure there is rule to keep the order of predecessors but I
> > can see Jump Threading pass generates different order of predecessors
> > on basic blocks.
> >
> > If llvm does not have the rule about the order of predecessors, it
> > seems VPlanNatviePath need to consider the different order of
> > predecessors. How do you think about it?
>
>
> Yes that seems like a bug. Could you create a bug repot at
https://bugs.llvm.org or share the reproducer here, if you don’t have an
account?
>
> Cheers,
> Florian