<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jun 10, 2015, at 6:17 PM, Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com" class="">sanjoy@playingwithpointers.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class="">I'm not sure if inbounds can be used to prove <nuw>. If an object<br class="">%OBJ is allocated at address -1 then "gep inbounds %OBJ 1" is not<br class="">poison, but the underlying computation unsigned-overflows.<br class=""></div></div></blockquote><div><br class=""></div><div>I think that this should yield poison per langref because the signed arithmetic implied by the indices should be performed with infinite precision. Base is treated as unsigned so 0xff…ff + 1 would be 0x100…00 which would be out of bounds (sort of). See also this which I think is even more explicit: <a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__llvm.org_docs_GetElementPtr.html-23what-2Dhappens-2Dif-2Da-2Dgep-2Dcomputation-2Doverflows&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=lvJKgPLtmT1JHdtUXb3NKJy7qicFonx2SlnLwtGCWi4&s=cjnz1mDvlPotkysLQLiq1tfA2nH1Zu0S0idlnDNUJ1A&e=" class="">http://llvm.org/docs/GetElementPtr.html#what-happens-if-a-gep-computation-overflows</a></div><div><br class=""></div><div>Adam</div><br class=""><blockquote type="cite" class=""><div class=""><div class="">It may be possible to use inbounds to derive <nsw> but that too is<br class="">tricky since inbounds does not directly imply anything about no-wrap<br class="">as far as I can tell.<br class=""><br class="">On Wed, Jun 10, 2015 at 5:29 PM, Adam Nemet <<a href="mailto:anemet@apple.com" class="">anemet@apple.com</a>> wrote:<br class=""><blockquote type="cite" class="">[+Arnold]<br class=""><br class=""><blockquote type="cite" class="">On Jun 10, 2015, at 1:29 PM, Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com" class="">sanjoy@playingwithpointers.com</a>> wrote:<br class=""><br class="">[+CC Andy]<br class=""><br class=""><blockquote type="cite" class="">Can anyone familiar with ScalarRevolution tell me whether this is an<br class="">expected behavior or a bug?<br class=""></blockquote><br class="">Assuming you're talking about 2*k, this is a bug. ScalarEvolution<br class="">should be able to prove that {0,+,4} is <nsw> and <nuw>.<br class=""></blockquote><br class="">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.<br class=""><br class="">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.<br class=""><br class="">A probably more interesting case is x[2*k] = x[2*k+2] + … which would require non-wrapping.<br class=""><br class="">Looks like we only consider an inbounds gep non-wrapping if it uses a unit stride. I am not sure why…<br class=""><br class="">Adam<br class=""><br class=""><blockquote type="cite" class=""><br class="">Part of the problem is that in this case ScalarEvolution does not try<br class="">to prove that {0,+,4} is <nsw> when the expression is constructed<br class="">(since proving that has non-trivial cost) [1]. To get ScalarEvolution<br class="">to try to prove that {0,+,4} has no-wrap properties, the client needs<br class="">to construct a sign-extend expression of {0,+,4}. SCEV will try to<br class="">change a sext of an add-rec to an add-rec of sexts and try to prove<br class="">no-wrap in the process [2].<br class=""><br class="">To easily do this from IR, you can just add a dummy sext instruction<br class="">(like in the IR fragment below) and run<br class="">'opt -analyze -scalar-evolution -scalar-evolution' (just running SCEV<br class="">won't dce the unused instruction):<br class=""><br class=""> ; ModuleID = '<stdin>'<br class=""> target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"<br class=""> target triple = "x86_64-apple-macosx10.10.0"<br class=""><br class=""> @x = common global [1024 x float] zeroinitializer, align 16<br class=""> @y = common global [1024 x float] zeroinitializer, align 16<br class=""><br class=""> ; Function Attrs: nounwind ssp uwtable<br class=""> define void @myloop1() {<br class=""> bb:<br class=""> br label %bb2<br class=""><br class=""> bb1: ; preds = %bb2<br class=""> ret void<br class=""><br class=""> bb2: ; preds = %bb2, %bb<br class=""> %k.01 = phi i64 [ 0, %bb ], [ %tmp15, %bb2 ]<br class=""> %tmp = shl nsw i64 %k.01, 1<br class=""> %dummy_sext = sext i64 %tmp to i128<br class=""> %tmp3 = getelementptr inbounds [1024 x float], [1024 x float]* @x,<br class="">i64 0, i64 %tmp<br class=""> %tmp4 = load float, float* %tmp3, align 16, !tbaa !2<br class=""> %tmp5 = getelementptr inbounds [1024 x float], [1024 x float]* @y,<br class="">i64 0, i64 %k.01<br class=""> %tmp6 = load float, float* %tmp5, align 8, !tbaa !2<br class=""> %tmp7 = fadd float %tmp4, %tmp6<br class=""> store float %tmp7, float* %tmp3, align 16, !tbaa !2<br class=""> %tmp8 = or i64 %k.01, 1<br class=""> %tmp9 = shl nsw i64 %tmp8, 1<br class=""> %tmp10 = getelementptr inbounds [1024 x float], [1024 x float]*<br class="">@x, i64 0, i64 %tmp9<br class=""> %tmp11 = load float, float* %tmp10, align 8, !tbaa !2<br class=""> %tmp12 = getelementptr inbounds [1024 x float], [1024 x float]*<br class="">@y, i64 0, i64 %tmp8<br class=""> %tmp13 = load float, float* %tmp12, align 4, !tbaa !2<br class=""> %tmp14 = fadd float %tmp11, %tmp13<br class=""> store float %tmp14, float* %tmp10, align 8, !tbaa !2<br class=""> %tmp15 = add nsw i64 %k.01, 2<br class=""> %exitcond.1 = icmp eq i64 %tmp15, 512<br class=""> br i1 %exitcond.1, label %bb1, label %bb2<br class=""> }<br class=""><br class=""> !0 = !{i32 1, !"PIC Level", i32 2}<br class=""> !1 = !{!"clang version 3.7.0 (clang-stage2-configure-Rlto_build 239114)"}<br class=""> !2 = !{!3, !3, i64 0}<br class=""> !3 = !{!"float", !4, i64 0}<br class=""> !4 = !{!"omnipotent char", !5, i64 0}<br class=""> !5 = !{!"Simple C/C++ TBAA"}<br class=""><br class=""><br class="">However, adding a dummy sext only proves <nuw> for {0,+,4} and not<br class=""><nsw>. The problem is that when constructing sext({0,+,4}) SCEV<br class="">realizes that since {0,+,4} is always positive, sext({0,+,4}) ==<br class="">zext({0,+,4}); and to change a zext of an add-rec to an add-rec of<br class="">zexts, SCEV only needs to prove <nuw> and not <nsw>.<br class=""><br class=""><br class="">I wonder if it makes sense to add a hook to SCEV that gets it to try<br class="">as hard as it can to prove <nuw> / <nsw> for specific add recurrences.<br class=""><br class=""><br class=""><br class="">[1]: It will try to prove nuw and nsw in cases where it is "easy", but<br class=""> not in this specific case.<br class=""><br class="">[2]: So a worthwhile project is to have the vectorizer construct sign<br class=""> extend expressions of add recurrences that it really cares about<br class=""> proving no-wrap of and then check the flags on the<br class=""> SCEVAddRecExpr. It may consume too much compile time, so there's<br class=""> a tricky trade-off here.<br class=""><br class=""><br class="">-- Sanjoy<br class="">_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:LLVMdev@cs.uiuc.edu" class="">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" class="">http://llvm.cs.uiuc.edu</a><br class=""><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" class="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br class=""></blockquote><br class=""></blockquote></div></div></blockquote></div><br class=""></body></html>