[llvm-dev] [SCEV] inconsistent operand ordering

[Sanjoy Das via llvm-dev]

Hi Pankaj,

Thanks for the detailed report and analysis.  I think I've fixed this specific issue in 284501.

However, if you see more cases like this, please don't hesitate to bring them up -- the ordering logic in SCEV should 
definitely be smart enough to handle all real world cases.

-- Sanjoy

Chawla, Pankaj via llvm-dev wrote:
> Hi,
>
> I noticed an inconsistency in how ScalarEvolution orders instruction operands. This inconsistency can result in creation
> of separate (%a * %b) and (%b * %a) SCEVs as demonstrated by the example IR below (attached as gep-phi.ll)-
>
> /target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"/
>
> //
>
> /define void @foo(i8* nocapture %arr, i32 %n, i32* %A, i32* %B) local_unnamed_addr {/
>
> /entry:/
>
> /%cmp10 = icmp sgt i32 %n, 0/
>
> /br i1 %cmp10, label %for.body.preheader, label %for.end/
>
> //
>
> /for.body.preheader: ; preds = %entry/
>
> /%a = load i32, i32* %A, align 4/
>
> /%b = load i32, i32* %B, align 4/
>
> /%mul = mul nsw i32 %b, %a/
>
> /%add.ptr = getelementptr inbounds i8, i8* %arr, i32 %mul/
>
> /br label %for.body/
>
> //
>
> /for.body: ; preds = %for.body, %for.body.preheader/
>
> /%q.012 = phi i8* [ %add.ptr2, %for.body ], [ %add.ptr, %for.body.preheader ]/
>
> /%i.011 = phi i32 [ %inc, %for.body ], [ 0, %for.body.preheader ]/
>
> /%conv = trunc i32 %i.011 to i8/
>
> /store i8 %conv, i8* %q.012, align 1/
>
> /%add.ptr2 = getelementptr inbounds i8, i8* %q.012, i32 %b/
>
> /%inc = add nuw nsw i32 %i.011, 1/
>
> /%exitcond = icmp eq i32 %inc, %n/
>
> /br i1 %exitcond, label %for.end.loopexit, label %for.body/
>
> //
>
> /for.end.loopexit: ; preds = %for.body/
>
> /br label %for.end/
>
> //
>
> /for.end: ; preds = %for.end.loopexit, %entry/
>
> /ret void/
>
> /}/
>
> For this IR, if I call getSCEV() in the following order-
>
> *1) getSCEV(%q.012)*
>
> 2) getSCEV(%add.ptr2)
>
> *3) getSCEV(%q.012)*
>
> The output I get is this-
>
> *{((%a * %b) + %arr)<nsw>,+,%b}<nw><%for.body>*
>
> {(((1 + %a) * %b) + %arr),+,%b}<nw><%for.body>
>
> *%q.012*
>
> Please note that we are getting a different SCEV for %q.012 based on the order of getSCEV() calls. This happens because
> in the second call to getSCEV(%q.012), ScalarEvolution tries to form the SCEV by shifting the SCEV of %add.ptr2 by
> performing this subtraction-
>
> (((1 + %a) * %b) - %b)
>
> This results in the creation of the swapped SCEV (%b * %a). A later pointer comparison between two (SCEV *) fails due to
> the presence of the swapped SCEV and we get the conservative SCEVUnknown %q.012.
>
> The easiest way to reproduce the issue is to apply the attached se.patch to the compiler which changes the print
> function of ScalarEvolution to print in this particular order and then execute this-
>
> $ opt -analyze -scalar-evolution gep-phi.ll
>
> The root cause of this issue is the function CompareSCEVComplexity(). The ordering for instruction operands is not very
> robust as acknowledged by the comment for this particular piece of code-
>
> // For instructions, compare their loop depth, and their operand
>
> // count. This is pretty loose.
>
> Can this be fixed?
>
> Thanks,
>
> Pankaj
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev