llvm dev - Jun 2015 - [LLVMdev] Question about NoWrap flag for SCEVAddRecExpr

I am testing vectorization on the following test case:

float x[1024], y[1024];

void myloop1() {
        for (long int k = 0; k < 512; k++) {
           x[2*k] = x[2*k]+y[k];
        }
}

Vectorization failed due to "unsafe dependent memory operation". I
traced
the LoopAccessAnalysis.cpp and found the reason is the NoWrapFlag for 
SCEVAddRecExpr is not set and consequently the dependence distant became 
unknown. 

Can anyone familiar with ScalarRevolution tell me whether this is an 
expected behavior or a bug? 

Tong
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150610/7949fbac/attachment.html>

[+CC Andy]
> Can anyone familiar with ScalarRevolution tell me whether this is an
> expected behavior or a bug?
Assuming you're talking about 2*k, this is a bug.  ScalarEvolution
should be able to prove that {0,+,4} is <nsw> and <nuw>.

Part of the problem is that in this case ScalarEvolution does not try
to prove that {0,+,4} is <nsw> when the expression is constructed
(since proving that has non-trivial cost) [1].  To get ScalarEvolution
to try to prove that {0,+,4} has no-wrap properties, the client needs
to construct a sign-extend expression of {0,+,4}.  SCEV will try to
change a sext of an add-rec to an add-rec of sexts and try to prove
no-wrap in the process [2].

To easily do this from IR, you can just add a dummy sext instruction
(like in the IR fragment below) and run
'opt -analyze -scalar-evolution -scalar-evolution' (just running SCEV
won't dce the unused instruction):

  ; ModuleID = '<stdin>'
  target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
  target triple = "x86_64-apple-macosx10.10.0"

  @x = common global [1024 x float] zeroinitializer, align 16
  @y = common global [1024 x float] zeroinitializer, align 16

  ; Function Attrs: nounwind ssp uwtable
  define void @myloop1() {
  bb:
    br label %bb2

  bb1:                                              ; preds = %bb2
    ret void

  bb2:                                              ; preds = %bb2, %bb
    %k.01 = phi i64 [ 0, %bb ], [ %tmp15, %bb2 ]
    %tmp = shl nsw i64 %k.01, 1
    %dummy_sext = sext i64 %tmp to i128
    %tmp3 = getelementptr inbounds [1024 x float], [1024 x float]* @x,
i64 0, i64 %tmp
    %tmp4 = load float, float* %tmp3, align 16, !tbaa !2
    %tmp5 = getelementptr inbounds [1024 x float], [1024 x float]* @y,
i64 0, i64 %k.01
    %tmp6 = load float, float* %tmp5, align 8, !tbaa !2
    %tmp7 = fadd float %tmp4, %tmp6
    store float %tmp7, float* %tmp3, align 16, !tbaa !2
    %tmp8 = or i64 %k.01, 1
    %tmp9 = shl nsw i64 %tmp8, 1
    %tmp10 = getelementptr inbounds [1024 x float], [1024 x float]*
@x, i64 0, i64 %tmp9
    %tmp11 = load float, float* %tmp10, align 8, !tbaa !2
    %tmp12 = getelementptr inbounds [1024 x float], [1024 x float]*
@y, i64 0, i64 %tmp8
    %tmp13 = load float, float* %tmp12, align 4, !tbaa !2
    %tmp14 = fadd float %tmp11, %tmp13
    store float %tmp14, float* %tmp10, align 8, !tbaa !2
    %tmp15 = add nsw i64 %k.01, 2
    %exitcond.1 = icmp eq i64 %tmp15, 512
    br i1 %exitcond.1, label %bb1, label %bb2
  }

  !0 = !{i32 1, !"PIC Level", i32 2}
  !1 = !{!"clang version 3.7.0 (clang-stage2-configure-Rlto_build
239114)"}
  !2 = !{!3, !3, i64 0}
  !3 = !{!"float", !4, i64 0}
  !4 = !{!"omnipotent char", !5, i64 0}
  !5 = !{!"Simple C/C++ TBAA"}


However, adding a dummy sext only proves <nuw> for {0,+,4} and not
<nsw>.  The problem is that when constructing sext({0,+,4}) SCEV
realizes that since {0,+,4} is always positive, sext({0,+,4}) =zext({0,+,4});
and to change a zext of an add-rec to an add-rec of
zexts, SCEV only needs to prove <nuw> and not <nsw>.


I wonder if it makes sense to add a hook to SCEV that gets it to try
as hard as it can to prove <nuw> / <nsw> for specific add
recurrences.



[1]: It will try to prove nuw and nsw in cases where it is "easy", but
     not in this specific case.

[2]: So a worthwhile project is to have the vectorizer construct sign
     extend expressions of add recurrences that it really cares about
     proving no-wrap of and then check the flags on the
     SCEVAddRecExpr.  It may consume too much compile time, so there's
     a tricky trade-off here.


-- Sanjoy

Hi Sanjoy,

Interesting. I took a closer look at SCEV when I saw Tong’s example. I’m curious
about "[1]: It will try to prove nuw and nsw in cases where it is
"easy", but not in this specific case.” Could you describe “easy” and
“difficult” algorithmically?

Thanks
Gerolf
> On Jun 10, 2015, at 1:29 PM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
> [+CC Andy]
> 
>> Can anyone familiar with ScalarRevolution tell me whether this is an
>> expected behavior or a bug?
> 
> Assuming you're talking about 2*k, this is a bug.  ScalarEvolution
> should be able to prove that {0,+,4} is <nsw> and <nuw>.
> 
> Part of the problem is that in this case ScalarEvolution does not try
> to prove that {0,+,4} is <nsw> when the expression is constructed
> (since proving that has non-trivial cost) [1].  To get ScalarEvolution
> to try to prove that {0,+,4} has no-wrap properties, the client needs
> to construct a sign-extend expression of {0,+,4}.  SCEV will try to
> change a sext of an add-rec to an add-rec of sexts and try to prove
> no-wrap in the process [2].
> 
> To easily do this from IR, you can just add a dummy sext instruction
> (like in the IR fragment below) and run
> 'opt -analyze -scalar-evolution -scalar-evolution' (just running
SCEV
> won't dce the unused instruction):
> 
>  ; ModuleID = '<stdin>'
>  target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
>  target triple = "x86_64-apple-macosx10.10.0"
> 
>  @x = common global [1024 x float] zeroinitializer, align 16
>  @y = common global [1024 x float] zeroinitializer, align 16
> 
>  ; Function Attrs: nounwind ssp uwtable
>  define void @myloop1() {
>  bb:
>    br label %bb2
> 
>  bb1:                                              ; preds = %bb2
>    ret void
> 
>  bb2:                                              ; preds = %bb2, %bb
>    %k.01 = phi i64 [ 0, %bb ], [ %tmp15, %bb2 ]
>    %tmp = shl nsw i64 %k.01, 1
>    %dummy_sext = sext i64 %tmp to i128
>    %tmp3 = getelementptr inbounds [1024 x float], [1024 x float]* @x,
> i64 0, i64 %tmp
>    %tmp4 = load float, float* %tmp3, align 16, !tbaa !2
>    %tmp5 = getelementptr inbounds [1024 x float], [1024 x float]* @y,
> i64 0, i64 %k.01
>    %tmp6 = load float, float* %tmp5, align 8, !tbaa !2
>    %tmp7 = fadd float %tmp4, %tmp6
>    store float %tmp7, float* %tmp3, align 16, !tbaa !2
>    %tmp8 = or i64 %k.01, 1
>    %tmp9 = shl nsw i64 %tmp8, 1
>    %tmp10 = getelementptr inbounds [1024 x float], [1024 x float]*
> @x, i64 0, i64 %tmp9
>    %tmp11 = load float, float* %tmp10, align 8, !tbaa !2
>    %tmp12 = getelementptr inbounds [1024 x float], [1024 x float]*
> @y, i64 0, i64 %tmp8
>    %tmp13 = load float, float* %tmp12, align 4, !tbaa !2
>    %tmp14 = fadd float %tmp11, %tmp13
>    store float %tmp14, float* %tmp10, align 8, !tbaa !2
>    %tmp15 = add nsw i64 %k.01, 2
>    %exitcond.1 = icmp eq i64 %tmp15, 512
>    br i1 %exitcond.1, label %bb1, label %bb2
>  }
> 
>  !0 = !{i32 1, !"PIC Level", i32 2}
>  !1 = !{!"clang version 3.7.0 (clang-stage2-configure-Rlto_build
239114)"}
>  !2 = !{!3, !3, i64 0}
>  !3 = !{!"float", !4, i64 0}
>  !4 = !{!"omnipotent char", !5, i64 0}
>  !5 = !{!"Simple C/C++ TBAA"}
> 
> 
> However, adding a dummy sext only proves <nuw> for {0,+,4} and not
> <nsw>.  The problem is that when constructing sext({0,+,4}) SCEV
> realizes that since {0,+,4} is always positive, sext({0,+,4}) =>
zext({0,+,4}); and to change a zext of an add-rec to an add-rec of
> zexts, SCEV only needs to prove <nuw> and not <nsw>.
> 
> 
> I wonder if it makes sense to add a hook to SCEV that gets it to try
> as hard as it can to prove <nuw> / <nsw> for specific add
recurrences.
> 
> 
> 
> [1]: It will try to prove nuw and nsw in cases where it is
"easy", but
>     not in this specific case.
> 
> [2]: So a worthwhile project is to have the vectorizer construct sign
>     extend expressions of add recurrences that it really cares about
>     proving no-wrap of and then check the flags on the
>     SCEVAddRecExpr.  It may consume too much compile time, so there's
>     a tricky trade-off here.
> 
> 
> -- Sanjoy
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[+Arnold]
> On Jun 10, 2015, at 1:29 PM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
> [+CC Andy]
> 
>> Can anyone familiar with ScalarRevolution tell me whether this is an
>> expected behavior or a bug?
> 
> Assuming you're talking about 2*k, this is a bug.  ScalarEvolution
> should be able to prove that {0,+,4} is <nsw> and <nuw>.
I also find it surprising that the inbounds gep does not allow us to prove nuw
of the pointer here.  LAA has logic for this.

Not to mention that we’re trying to figure out the distance of x[2*k] against
*itself* which should be zero regardless of wrapping.

A probably more interesting case is x[2*k] = x[2*k+2] + … which would require
non-wrapping.

Looks like we only consider an inbounds gep non-wrapping if it uses a unit
stride.  I am not sure why…

Adam
> 
> Part of the problem is that in this case ScalarEvolution does not try
> to prove that {0,+,4} is <nsw> when the expression is constructed
> (since proving that has non-trivial cost) [1].  To get ScalarEvolution
> to try to prove that {0,+,4} has no-wrap properties, the client needs
> to construct a sign-extend expression of {0,+,4}.  SCEV will try to
> change a sext of an add-rec to an add-rec of sexts and try to prove
> no-wrap in the process [2].
> 
> To easily do this from IR, you can just add a dummy sext instruction
> (like in the IR fragment below) and run
> 'opt -analyze -scalar-evolution -scalar-evolution' (just running
SCEV
> won't dce the unused instruction):
> 
>  ; ModuleID = '<stdin>'
>  target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
>  target triple = "x86_64-apple-macosx10.10.0"
> 
>  @x = common global [1024 x float] zeroinitializer, align 16
>  @y = common global [1024 x float] zeroinitializer, align 16
> 
>  ; Function Attrs: nounwind ssp uwtable
>  define void @myloop1() {
>  bb:
>    br label %bb2
> 
>  bb1:                                              ; preds = %bb2
>    ret void
> 
>  bb2:                                              ; preds = %bb2, %bb
>    %k.01 = phi i64 [ 0, %bb ], [ %tmp15, %bb2 ]
>    %tmp = shl nsw i64 %k.01, 1
>    %dummy_sext = sext i64 %tmp to i128
>    %tmp3 = getelementptr inbounds [1024 x float], [1024 x float]* @x,
> i64 0, i64 %tmp
>    %tmp4 = load float, float* %tmp3, align 16, !tbaa !2
>    %tmp5 = getelementptr inbounds [1024 x float], [1024 x float]* @y,
> i64 0, i64 %k.01
>    %tmp6 = load float, float* %tmp5, align 8, !tbaa !2
>    %tmp7 = fadd float %tmp4, %tmp6
>    store float %tmp7, float* %tmp3, align 16, !tbaa !2
>    %tmp8 = or i64 %k.01, 1
>    %tmp9 = shl nsw i64 %tmp8, 1
>    %tmp10 = getelementptr inbounds [1024 x float], [1024 x float]*
> @x, i64 0, i64 %tmp9
>    %tmp11 = load float, float* %tmp10, align 8, !tbaa !2
>    %tmp12 = getelementptr inbounds [1024 x float], [1024 x float]*
> @y, i64 0, i64 %tmp8
>    %tmp13 = load float, float* %tmp12, align 4, !tbaa !2
>    %tmp14 = fadd float %tmp11, %tmp13
>    store float %tmp14, float* %tmp10, align 8, !tbaa !2
>    %tmp15 = add nsw i64 %k.01, 2
>    %exitcond.1 = icmp eq i64 %tmp15, 512
>    br i1 %exitcond.1, label %bb1, label %bb2
>  }
> 
>  !0 = !{i32 1, !"PIC Level", i32 2}
>  !1 = !{!"clang version 3.7.0 (clang-stage2-configure-Rlto_build
239114)"}
>  !2 = !{!3, !3, i64 0}
>  !3 = !{!"float", !4, i64 0}
>  !4 = !{!"omnipotent char", !5, i64 0}
>  !5 = !{!"Simple C/C++ TBAA"}
> 
> 
> However, adding a dummy sext only proves <nuw> for {0,+,4} and not
> <nsw>.  The problem is that when constructing sext({0,+,4}) SCEV
> realizes that since {0,+,4} is always positive, sext({0,+,4}) =>
zext({0,+,4}); and to change a zext of an add-rec to an add-rec of
> zexts, SCEV only needs to prove <nuw> and not <nsw>.
> 
> 
> I wonder if it makes sense to add a hook to SCEV that gets it to try
> as hard as it can to prove <nuw> / <nsw> for specific add
recurrences.
> 
> 
> 
> [1]: It will try to prove nuw and nsw in cases where it is
"easy", but
>     not in this specific case.
> 
> [2]: So a worthwhile project is to have the vectorizer construct sign
>     extend expressions of add recurrences that it really cares about
>     proving no-wrap of and then check the flags on the
>     SCEVAddRecExpr.  It may consume too much compile time, so there's
>     a tricky trade-off here.
> 
> 
> -- Sanjoy
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev