[SCEV] Search operand tree for scope bound when inferring flags from IR

[reames]

Summary

This does the obvious thing, and recurses through operands searching for a tighter bound on the defining scope. I'm honestly surprised by how little this seems to mater. I think it's worth doing for completeness, but I have to admit the test diffs are unconvincing.

[reames]

rebase over previous changes and tests

[nikic]

Why does this not recover this regression? https://reviews.llvm.org/D109789#inline-1056586 I would have thought that looking through the mul/zext would have helped there.

[reames]

In D111191#3046317, @nikic wrote:

Why does this not recover this regression? https://reviews.llvm.org/D109789#inline-1056586 I would have thought that looking through the mul/zext would have helped there.

Not sure, but it looks to be some negative interaction of PSE and LoopAccessAnalysis. The actual SCEV's look fine.

$ ./opt -enable-new-pm=0 -analyze -scalar-evolution scev-reduced.ll
Printing analysis 'Scalar Evolution Analysis' for function 'test1':
Classifying expressions for: @test1
....

%arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom
-->  ((4 * (zext i32 {1,+,1}<%for.body> to i64))<nuw><nsw> + %a)<nuw> U: full-set S: full-set		Exits: <<Unknown>>		LoopDispositions: { %for.body: Computable }

edit: actually, it does fix it. However lit does a prefix match not an exact match and the way the test line is written, that matches both regressed and unregressed. I'll update the test to show the more precise form. Good catch!

[reames]

hand tweak test to show improvement noted by @nikic

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

6605

Is an else missing here? We probably don't want to recurse through addrecs here, as the addrec will already have the smallest scope.

6613

Huh, I'm surprised we don't have a simpler way to write this.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

6605

Er, yes, yes it is. Good catch. :)

6613

Me too honestly. Closest alternative I could find was to use a visitor to recurse through all the operands, but that seemed worse.

[reames]

rebase

[nikic]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

6630

nit: This newline probably shouldn't be here.

[xbolva00]

llvm/test/Analysis/LoopAccessAnalysis/memcheck-wrapping-pointers.ll

19

Here we say nsw

48

And here nuw..

Suspicous.

[nikic]

llvm/test/Analysis/LoopAccessAnalysis/memcheck-wrapping-pointers.ll

48

The comment above is indeed outdated, but nuw is correct here. This is because inbounds only guarantees no overflow in the unsigned address space (despite the index being signed).

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::getNonTrivialDefiningScopeBound(const SCEV *S) {
   if (auto *U = dyn_cast<SCEVUnknown>(S))
     if (auto *I = dyn_cast<Instruction>(U->getValue()))
       return I;
   return nullptr;
 }
 
 const Instruction *
 ScalarEvolution::getDefiningScopeBound(ArrayRef<const SCEV *> Ops) {
-  const Instruction *Bound = nullptr;
+  // Do a bounded search of the def relation of the requested SCEVs.
+  SmallSet<const SCEV *, 16> Visited;
+  SmallVector<const SCEV *> Worklist;
+  auto pushOp = [&](const SCEV *S) {
+    if (!Visited.insert(S).second)
+      return;
+    // Threshold of 30 here is arbitrary.
+    if (Visited.size() > 30)
+      return;
+    Worklist.push_back(S);
+  };
+
   for (auto *S : Ops)
-    if (auto *DefI = getNonTrivialDefiningScopeBound(S))
+    pushOp(S);
+
+  const Instruction *Bound = nullptr;
+  while (!Worklist.empty()) {
+    auto *S = Worklist.pop_back_val();
+    if (auto *DefI = getNonTrivialDefiningScopeBound(S)) {
       if (!Bound || DT.dominates(Bound, DefI))
         Bound = DefI;
+    } else if (auto *S2 = dyn_cast<SCEVCastExpr>(S))
+      for (auto *Op : S2->operands())
+        pushOp(Op);
+    else if (auto *S2 = dyn_cast<SCEVNAryExpr>(S))
+      for (auto *Op : S2->operands())
+        pushOp(Op);
+    else if (auto *S2 = dyn_cast<SCEVUDivExpr>(S))
+      for (auto *Op : S2->operands())
+        pushOp(Op);
+
+  }
   return Bound ? Bound : &*F.getEntryBlock().begin();
 }
 
 
 static bool
 isGuaranteedToTransferExecutionToSuccessor(BasicBlock::const_iterator Begin,
                                            BasicBlock::const_iterator End) {
   // Limit number of instructions we look at, to avoid scanning through large

llvm/test/Analysis/LoopAccessAnalysis/memcheck-wrapping-pointers.ll

 ; If accesses to a and b can alias, we need to emit a run-time alias check
 ; between accesses to a and b. However, when i and i + 1 can wrap, their
 ; SCEV expression is not an AddRec. We need to create SCEV predicates and
 ; coerce the expressions to AddRecs in order to be able to emit the run-time
 ; alias check.
 ;
 ; The accesses at b[i] and a[i+1] correspond to the addresses %arrayidx and
 ; %arrayidx4 in the test. The SCEV expressions for these are:
 ;  ((4 * (zext i32 {1,+,1}<%for.body> to i64))<nuw><nsw> + %a)<nsw>
 ;  ((4 * (zext i32 {0,+,1}<%for.body> to i64))<nuw><nsw> + %b)<nsw>
 ;
 ; The transformed expressions are:
 ;  i64 {(4 + %a),+,4}<%for.body>
 ;  i64 {(4 + %b),+,4}<%for.body>
 
 ; CHECK-LABEL: test1
 ; CHECK:         Memory dependences are safe with run-time checks

 ; CHECK-NEXT:        (Low: %b High: ((4 * (1 umax %x)) + %b))
 ; CHECK-NEXT:          Member: {%b,+,4}<%for.body>
 ; CHECK:         Non vectorizable stores to invariant address were not found in loop.
 ; CHECK-NEXT:    SCEV assumptions:
 ; CHECK-NEXT:    {1,+,1}<%for.body> Added Flags: <nusw>
 ; CHECK-NEXT:    {0,+,1}<%for.body> Added Flags: <nusw>
 ; CHECK:         Expressions re-written:
 ; CHECK-NEXT:    [PSE]  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom:
-; CHECK-NEXT:      ((4 * (zext i32 {1,+,1}<%for.body> to i64))<nuw><nsw> + %a)
+; CHECK-NEXT:      ((4 * (zext i32 {1,+,1}<%for.body> to i64))<nuw><nsw> + %a)<nuw>
 ; CHECK-NEXT:      --> {(4 + %a),+,4}<%for.body>
 ; CHECK-NEXT:    [PSE]  %arrayidx4 = getelementptr inbounds i32, i32* %b, i64 %conv11:
-; CHECK-NEXT:      ((4 * (zext i32 {0,+,1}<%for.body> to i64))<nuw><nsw> + %b)
+; CHECK-NEXT:      ((4 * (zext i32 {0,+,1}<%for.body> to i64))<nuw><nsw> + %b)<nuw>
 ; CHECK-NEXT:      --> {%b,+,4}<%for.body>
 define void @test1(i64 %x, i32* %a, i32* %b) {
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body.preheader, %for.body
   %conv11 = phi i64 [ %conv, %for.body ], [ 0, %entry ]
   %i.010 = phi i32 [ %add, %for.body ], [ 0, %entry ]

llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll

 define noundef i64 @add-zext-recurse(i64 %arg) {
 ; CHECK-LABEL: 'add-zext-recurse'
 ; CHECK-NEXT:  Classifying expressions for: @add-zext-recurse
 ; CHECK-NEXT:    %a = load i32, i32* @gA, align 4
 ; CHECK-NEXT:    --> %a U: full-set S: full-set
 ; CHECK-NEXT:    %x = zext i32 %a to i64
 ; CHECK-NEXT:    --> (zext i32 %a to i64) U: [0,4294967296) S: [0,4294967296)
 ; CHECK-NEXT:    %res = add nuw i64 %x, %arg
-; CHECK-NEXT:    --> ((zext i32 %a to i64) + %arg) U: full-set S: full-set
+; CHECK-NEXT:    --> ((zext i32 %a to i64) + %arg)<nuw> U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @add-zext-recurse
 ;
   call void @foo()
   %a = load i32, i32* @gA
   %x = zext i32 %a to i64
   %res = add nuw i64 %x, %arg
   ret i64 %res
 }
 
 define noundef i64 @add-sext-recurse(i64 %arg) {
 ; CHECK-LABEL: 'add-sext-recurse'
 ; CHECK-NEXT:  Classifying expressions for: @add-sext-recurse
 ; CHECK-NEXT:    %a = load i32, i32* @gA, align 4
 ; CHECK-NEXT:    --> %a U: full-set S: full-set
 ; CHECK-NEXT:    %x = sext i32 %a to i64
 ; CHECK-NEXT:    --> (sext i32 %a to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
 ; CHECK-NEXT:    %res = add nuw i64 %x, %arg
-; CHECK-NEXT:    --> ((sext i32 %a to i64) + %arg) U: full-set S: full-set
+; CHECK-NEXT:    --> ((sext i32 %a to i64) + %arg)<nuw> U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @add-sext-recurse
 ;
   call void @foo()
   %a = load i32, i32* @gA
   %x = sext i32 %a to i64
   %res = add nuw i64 %x, %arg
   ret i64 %res
 }
 
 define noundef i16 @add-trunc-recurse() {
 ; CHECK-LABEL: 'add-trunc-recurse'
 ; CHECK-NEXT:  Classifying expressions for: @add-trunc-recurse
 ; CHECK-NEXT:    %a = load i32, i32* @gA, align 4
 ; CHECK-NEXT:    --> %a U: full-set S: full-set
 ; CHECK-NEXT:    %x = trunc i32 %a to i16
 ; CHECK-NEXT:    --> (trunc i32 %a to i16) U: full-set S: full-set
 ; CHECK-NEXT:    %res = add nuw i16 %x, 1
-; CHECK-NEXT:    --> (1 + (trunc i32 %a to i16)) U: full-set S: full-set
+; CHECK-NEXT:    --> (1 + (trunc i32 %a to i16))<nuw> U: [1,0) S: [1,0)
 ; CHECK-NEXT:  Determining loop execution counts for: @add-trunc-recurse
 ;
   call void @foo()
   %a = load i32, i32* @gA
   %x = trunc i32 %a to i16
   %res = add nuw i16 %x, 1
   ret i16 %res
 }
 
 define noundef i32 @add-udiv-recurse(i32 %arg) {
 ; CHECK-LABEL: 'add-udiv-recurse'
 ; CHECK-NEXT:  Classifying expressions for: @add-udiv-recurse
 ; CHECK-NEXT:    %a = load i32, i32* @gA, align 4
 ; CHECK-NEXT:    --> %a U: full-set S: full-set
 ; CHECK-NEXT:    %x = udiv i32 %a, %arg
 ; CHECK-NEXT:    --> (%a /u %arg) U: full-set S: full-set
 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
-; CHECK-NEXT:    --> (1 + (%a /u %arg)) U: full-set S: full-set
+; CHECK-NEXT:    --> (1 + (%a /u %arg))<nuw> U: [1,0) S: [1,0)
 ; CHECK-NEXT:  Determining loop execution counts for: @add-udiv-recurse
 ;
   call void @foo()
   %a = load i32, i32* @gA
   %x = udiv i32 %a, %arg
   %res = add nuw i32 %x, 1
   ret i32 %res
 }
 
 define noundef i32 @add-mul-recurse() {
 ; CHECK-LABEL: 'add-mul-recurse'
 ; CHECK-NEXT:  Classifying expressions for: @add-mul-recurse
 ; CHECK-NEXT:    %a = load i32, i32* @gA, align 4
 ; CHECK-NEXT:    --> %a U: full-set S: full-set
 ; CHECK-NEXT:    %x = mul i32 %a, 3
 ; CHECK-NEXT:    --> (3 * %a) U: full-set S: full-set
 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
-; CHECK-NEXT:    --> (1 + (3 * %a)) U: full-set S: full-set
+; CHECK-NEXT:    --> (1 + (3 * %a))<nuw> U: [1,0) S: [1,0)
 ; CHECK-NEXT:  Determining loop execution counts for: @add-mul-recurse
 ;
   call void @foo()
   %a = load i32, i32* @gA
   %x = mul i32 %a, 3
   %res = add nuw i32 %x, 1
   ret i32 %res
 }
 
 declare i32 @llvm.smin.i32(i32, i32)
 declare i32 @llvm.smax.i32(i32, i32)
 declare i32 @llvm.umin.i32(i32, i32)
 declare i32 @llvm.umax.i32(i32, i32)
 
 define noundef i32 @add-smin-recurse(i32 %arg) {
 ; CHECK-LABEL: 'add-smin-recurse'
 ; CHECK-NEXT:  Classifying expressions for: @add-smin-recurse
 ; CHECK-NEXT:    %a = load i32, i32* @gA, align 4
 ; CHECK-NEXT:    --> %a U: full-set S: full-set
 ; CHECK-NEXT:    %x = call i32 @llvm.smin.i32(i32 %a, i32 %arg)
 ; CHECK-NEXT:    --> (%arg smin %a) U: full-set S: full-set
 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
-; CHECK-NEXT:    --> (1 + (%arg smin %a)) U: full-set S: full-set
+; CHECK-NEXT:    --> (1 + (%arg smin %a))<nuw> U: [1,0) S: [1,0)
 ; CHECK-NEXT:  Determining loop execution counts for: @add-smin-recurse
 ;
   call void @foo()
   %a = load i32, i32* @gA
   %x = call i32 @llvm.smin.i32(i32 %a, i32 %arg)
   %res = add nuw i32 %x, 1
   ret i32 %res
 }
 
 define noundef i32 @add-smax-recurse(i32 %arg) {
 ; CHECK-LABEL: 'add-smax-recurse'
 ; CHECK-NEXT:  Classifying expressions for: @add-smax-recurse
 ; CHECK-NEXT:    %a = load i32, i32* @gA, align 4
 ; CHECK-NEXT:    --> %a U: full-set S: full-set
 ; CHECK-NEXT:    %x = call i32 @llvm.smax.i32(i32 %a, i32 %arg)
 ; CHECK-NEXT:    --> (%arg smax %a) U: full-set S: full-set
 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
-; CHECK-NEXT:    --> (1 + (%arg smax %a)) U: full-set S: full-set
+; CHECK-NEXT:    --> (1 + (%arg smax %a))<nuw> U: [1,0) S: [1,0)
 ; CHECK-NEXT:  Determining loop execution counts for: @add-smax-recurse
 ;
   call void @foo()
   %a = load i32, i32* @gA
   %x = call i32 @llvm.smax.i32(i32 %a, i32 %arg)
   %res = add nuw i32 %x, 1
   ret i32 %res
 }
 
 define noundef i32 @add-umin-recurse(i32 %arg) {
 ; CHECK-LABEL: 'add-umin-recurse'
 ; CHECK-NEXT:  Classifying expressions for: @add-umin-recurse
 ; CHECK-NEXT:    %a = load i32, i32* @gA, align 4
 ; CHECK-NEXT:    --> %a U: full-set S: full-set
 ; CHECK-NEXT:    %x = call i32 @llvm.umin.i32(i32 %a, i32 %arg)
 ; CHECK-NEXT:    --> (%arg umin %a) U: full-set S: full-set
 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
-; CHECK-NEXT:    --> (1 + (%arg umin %a)) U: full-set S: full-set
+; CHECK-NEXT:    --> (1 + (%arg umin %a))<nuw> U: [1,0) S: [1,0)
 ; CHECK-NEXT:  Determining loop execution counts for: @add-umin-recurse
 ;
   call void @foo()
   %a = load i32, i32* @gA
   %x = call i32 @llvm.umin.i32(i32 %a, i32 %arg)
   %res = add nuw i32 %x, 1
   ret i32 %res
 }
 
 define noundef i32 @add-umax-recurse(i32 %arg) {
 ; CHECK-LABEL: 'add-umax-recurse'
 ; CHECK-NEXT:  Classifying expressions for: @add-umax-recurse
 ; CHECK-NEXT:    %a = load i32, i32* @gA, align 4
 ; CHECK-NEXT:    --> %a U: full-set S: full-set
 ; CHECK-NEXT:    %x = call i32 @llvm.umax.i32(i32 %a, i32 %arg)
 ; CHECK-NEXT:    --> (%arg umax %a) U: full-set S: full-set
 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
-; CHECK-NEXT:    --> (1 + (%arg umax %a)) U: full-set S: full-set
+; CHECK-NEXT:    --> (1 + (%arg umax %a))<nuw> U: [1,0) S: [1,0)
 ; CHECK-NEXT:  Determining loop execution counts for: @add-umax-recurse
 ;
   call void @foo()
   %a = load i32, i32* @gA
   %x = call i32 @llvm.umax.i32(i32 %a, i32 %arg)
   %res = add nuw i32 %x, 1
   ret i32 %res
 }

 ; CHECK-NEXT:    --> %c U: full-set S: full-set
 ; CHECK-NEXT:    %d = load i32, i32* @gD, align 4
 ; CHECK-NEXT:    --> %d U: full-set S: full-set
 ; CHECK-NEXT:    %x = add nuw i32 %a, %b
 ; CHECK-NEXT:    --> (%a + %b)<nuw> U: full-set S: full-set
 ; CHECK-NEXT:    %y = add nuw i32 %c, %d
 ; CHECK-NEXT:    --> (%c + %d)<nuw> U: full-set S: full-set
 ; CHECK-NEXT:    %res = add nuw i32 %x, %y
-; CHECK-NEXT:    --> (%a + %b + %c + %d) U: full-set S: full-set
+; CHECK-NEXT:    --> (%a + %b + %c + %d)<nuw> U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @add-recurse-inline
 ;
   call void @foo()
   %a = load i32, i32* @gA
   %b = load i32, i32* @gB
   %c = load i32, i32* @gC
   %d = load i32, i32* @gD
 
   %x = add nuw i32 %a, %b
   %y = add nuw i32 %c, %d
   %res = add nuw i32 %x, %y
   ret i32 %res
 }