llvm dev - Feb 2021 - SCEV determines the inner loop induction variable to be loop-invariant at the scope of the outer loop

Dear all,



For the following IR which is essentially a doubly nested loop, if we get
the SCEV expression for the inner loop induction variable, i.e., %j.018, at
the scope of the outer loop using getSCEVAtScope(), the result is: 9. That
is a constant, or loop-invariant.


However, %j.018 does keep changing within the scope of the outer loop since
it is the induction variable of the inner loop, so it is not
straightforward to me why %j.018 is considered a loop-invariant. Something
like “{0,+,1}<nuw><nsw><%for.body4>” would make more sense to
me.



I’m wondering if I can get any comments on that?



Best regards,

Congzhe



***************************************************************

define dso_local i32 @main() {

entry:

  br label %for.cond1.preheader



for.cond1.preheader:                              ; preds %for.cond.cleanup3,
%entry

  %i.020 = phi i32 [ 0, %entry ], [ %inc8, %for.cond.cleanup3 ]

  %x.019 = phi i32 [ 17, %entry ], [ %add, %for.cond.cleanup3 ]

  br label %for.body4



for.cond.cleanup:                                 ; preds %for.cond.cleanup3

  ret i32 %add



for.cond.cleanup3:                                ; preds = %for.body4

  %inc8 = add nuw nsw i32 %i.020, 1

  %exitcond21 = icmp eq i32 %inc8, 10

  br i1 %exitcond21, label %for.cond.cleanup, label %for.cond1.preheader



for.body4:                                        ; preds = %for.body4,
%for.cond1.preheader

  %j.018 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body4 ]

  %x.117 = phi i32 [ %x.019, %for.cond1.preheader ], [ %add, %for.body4 ]

  %cmp5 = icmp eq i64 %j.018, 9

  %conv = zext i1 %cmp5 to i32

  %add = add nsw i32 %x.117, %conv

  call void @_Z3foov()

  %inc = add nuw nsw i64 %j.018, 1

  %exitcond = icmp eq i64 %inc, 10

  br i1 %exitcond, label %for.cond.cleanup3, label %for.body4

}



declare dso_local void @_Z3foov() local_unnamed_addr #1
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210202/74d62a29/attachment.html>

%j.018 is variant in the innermost loop (for.body4), but after
existing that loop, it will have the value before leaving the loop. If
you intent to use %j.018 in the innermost loop, you need to call
getSCEVAtScope() with the innermost loop as the scope. getSCEVAtScope
with a scope outside the loop (or NULL) will try to derive the exit
value.

Michael



Am Mi., 3. Feb. 2021 um 11:11 Uhr schrieb congzhe cao via llvm-dev
<llvm-dev at lists.llvm.org>:
>
> Dear all,
>
>
>
> For the following IR which is essentially a doubly nested loop, if we get
the SCEV expression for the inner loop induction variable, i.e., %j.018, at the
scope of the outer loop using getSCEVAtScope(), the result is: 9. That is a
constant, or loop-invariant.
>
>
> However, %j.018 does keep changing within the scope of the outer loop since
it is the induction variable of the inner loop, so it is not straightforward to
me why %j.018 is considered a loop-invariant. Something like
“{0,+,1}<nuw><nsw><%for.body4>” would make more sense to me.
>
>
>
> I’m wondering if I can get any comments on that?
>
>
>
> Best regards,
>
> Congzhe
>
>
>
> ***************************************************************
>
> define dso_local i32 @main() {
>
> entry:
>
>   br label %for.cond1.preheader
>
>
>
> for.cond1.preheader:                              ; preds =
%for.cond.cleanup3, %entry
>
>   %i.020 = phi i32 [ 0, %entry ], [ %inc8, %for.cond.cleanup3 ]
>
>   %x.019 = phi i32 [ 17, %entry ], [ %add, %for.cond.cleanup3 ]
>
>   br label %for.body4
>
>
>
> for.cond.cleanup:                                 ; preds =
%for.cond.cleanup3
>
>   ret i32 %add
>
>
>
> for.cond.cleanup3:                                ; preds = %for.body4
>
>   %inc8 = add nuw nsw i32 %i.020, 1
>
>   %exitcond21 = icmp eq i32 %inc8, 10
>
>   br i1 %exitcond21, label %for.cond.cleanup, label %for.cond1.preheader
>
>
>
> for.body4:                                        ; preds = %for.body4,
%for.cond1.preheader
>
>   %j.018 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body4 ]
>
>   %x.117 = phi i32 [ %x.019, %for.cond1.preheader ], [ %add, %for.body4 ]
>
>   %cmp5 = icmp eq i64 %j.018, 9
>
>   %conv = zext i1 %cmp5 to i32
>
>   %add = add nsw i32 %x.117, %conv
>
>   call void @_Z3foov()
>
>   %inc = add nuw nsw i64 %j.018, 1
>
>   %exitcond = icmp eq i64 %inc, 10
>
>   br i1 %exitcond, label %for.cond.cleanup3, label %for.body4
>
> }
>
>
>
> declare dso_local void @_Z3foov() local_unnamed_addr #1
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev