[Attributor] Deal with shrinking dereferenceability in a loop

[jdoerfert]

Summary

If we have a loop in which the dereferenceability of a pointer decreases
we did slowly increase it so far, leading to a timeout during the
fixpoint iteration. With this patch we detect such circular reasoning
and indicate a fixpoint early.

[uenoku]

LGTM

llvm/lib/Transforms/IPO/Attributor.cpp

auto VisitValueCB = [&](Value &V, DerefState &T, bool Stripped) -> bool {
         const DerefState &DS = static_cast<const DerefState &>(AA.getState());
         DerefBytes = DS.DerefBytesState.getAssumed();
         T.GlobalState &= DS.GlobalState;
       }
 
       // For now we do not try to "increase" dereferenceability due to negative
       // indices as we first have to come up with code to deal with loops and
       // for overflows of the dereferenceable bytes.
-      if (Offset.getSExtValue() < 0)
+      int64_t OffsetSExt = Offset.getSExtValue();
+      if (OffsetSExt < 0)
         Offset = 0;
 
       T.takeAssumedDerefBytesMinimum(
-          std::max(int64_t(0), DerefBytes - Offset.getSExtValue()));
+          std::max(int64_t(0), DerefBytes - OffsetSExt));
 
-      if (!Stripped && this == &AA) {
+      if (this == &AA) {
+        if (!Stripped) {
+          // If nothing was stripped IR information is all we got.
           T.takeKnownDerefBytesMaximum(
-            std::max(int64_t(0), DerefBytes - Offset.getSExtValue()));
+              std::max(int64_t(0), DerefBytes - OffsetSExt));
+          T.indicatePessimisticFixpoint();
+        } else if (OffsetSExt > 0) {
+          // If something was stripped but there is circular reasoning we look
+          // for the offset. If it is positive we basically decrease the
+          // dereferenceable bytes in a circluar loop now, which will simply
+          // drive them down to the known value in a very slow way which we
+          // can accelerate.
           T.indicatePessimisticFixpoint();
         }
+      }
 
       return T.isValidState();
     };
 
     DerefState T;
     if (!genericValueTraversal<AADereferenceable, DerefState>(
             A, getIRPosition(), *this, T, VisitValueCB))
       return indicatePessimisticFixpoint();

llvm/test/Transforms/FunctionAttrs/dereferenceable.ll

 ; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations=4 -S < %s | FileCheck %s --check-prefixes=ATTRIBUTOR
 
 
+declare void @deref_phi_user(i32* %a);
+
 ; TEST 1
 ; take mininimum of return values
 ;
 define i32* @test1(i32* dereferenceable(4) %0, double* dereferenceable(8) %1, i1 zeroext %2) local_unnamed_addr {
 ; ATTRIBUTOR: define nonnull dereferenceable(4) i32* @test1(i32* nonnull dereferenceable(4) %0, double* nonnull dereferenceable(8) %1, i1 zeroext %2)
   %4 = bitcast double* %1 to i32*
   %5 = select i1 %2, i32* %0, i32* %4
   ret i32* %5

 
 define dereferenceable(4) i32* @test4(i32* dereferenceable(8) %0) local_unnamed_addr {
 ; ATTRIBUTOR: define nonnull dereferenceable(8) i32* @test4(i32* nonnull returned dereferenceable(8) %0)
   ret i32* %0
 }
 
 ; TEST 5
 ; loop in which dereferenceabily "grows"
-declare void @deref_phi_user(i32* %a);
-define void @deref_phi(i32* dereferenceable(4000) %a) {
+define void @deref_phi_growing(i32* dereferenceable(4000) %a) {
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc, %entry
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
   %a.addr.0 = phi i32* [ %a, %entry ], [ %incdec.ptr, %for.inc ]
 ; CHECK: call void @deref_phi_user(i32* dereferenceable(4000) %a.addr.0)
   call void @deref_phi_user(i32* %a.addr.0)

 for.inc:                                          ; preds = %for.body
   %incdec.ptr = getelementptr inbounds i32, i32* %a.addr.0, i64 -1
   %inc = add nuw nsw i32 %i.0, 1
   br label %for.cond
 
 for.end:                                          ; preds = %for.cond.cleanup
   ret void
 }
+
+; TEST 6
+; loop in which dereferenceabily "shrinks"
+define void @deref_phi_shrinking(i32* dereferenceable(4000) %a) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %a.addr.0 = phi i32* [ %a, %entry ], [ %incdec.ptr, %for.inc ]
+; CHECK: call void @deref_phi_user(i32* %a.addr.0)
+  call void @deref_phi_user(i32* %a.addr.0)
+  %tmp = load i32, i32* %a.addr.0, align 4
+  %cmp = icmp slt i32 %i.0, %tmp
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond
+  br label %for.end
+
+for.body:                                         ; preds = %for.cond
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %incdec.ptr = getelementptr inbounds i32, i32* %a.addr.0, i64 1
+  %inc = add nuw nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond.cleanup
+  ret void
+}