[FunctionAttrs] Fix an iterator wraparound bug

[sanjoy]

Summary

This change fixes an iterator wraparound bug in
determinePointerReadAttrs.

Ideally, ++'ing off the end() of an iplist should result in a failed
assert, but currently iplist seems to silently wrap to the head of the
list on end()++. This is why the bad behavior is difficult to
demonstrate.

[reames]

lib/Transforms/IPO/FunctionAttrs.cpp

445 ↗

(On Diff #39260)

I would rather we just gave up on VarArg callsites unless you have a compelling reason we need to handle them here. Return a conservative answer, and let someone else refine it later.

p.s. Does the other patch have the same issue?

[sanjoy]

lib/Transforms/IPO/FunctionAttrs.cpp

445 ↗

(On Diff #39260)

I didn't add the code, so I'm not in a position to judge whether there is a compelling reason for this optimization or not. :)

Moreover, bailing out unconditionally on varargs functions breaks test/Transforms/FunctionAttrs/readattrs.ll (added by @nlewycky in Jul 2013), and I'd rather not pessimize transforms that have in-tree tests.

p.s. Does the other patch have the same issue?

If you mean D14306, then I don't think so -- that change is fine as far as I can tell.

[dblaikie]

+Duncan, who's been mucking about with llvm's ilist issues recently

[reames]

LGTM. Minor comment below on an improved structured, but the current code is correct and strictly better than what we have.

lib/Transforms/IPO/FunctionAttrs.cpp

446 ↗

(On Diff #39260)

I think this would be far clearer as:
for (non var arg arguments) { do previous code)
for (var arg arguments) { return nope! }

[sanjoy]

lib/Transforms/IPO/FunctionAttrs.cpp

446 ↗

(On Diff #39260)

Yeah, that's a good idea. I'll do that restructuring and check in.

[sanjoy]

Actually, I think it will be cleaner to do the same fix I did in D14363 here as well, since we have a direct pointer to the Use * here as well. It won't quite be NFC, since we'll enter the worklist loop multiple times for the same value in cases like

call void @f(i32* readonly nocapture %x, i32* %x)

so it may slightly regress compile time if the second use of %x was a vararg argument. But I think it will make the code easier to read.

[sanjoy]

• A cleaner fix. Sending for re-review since this is different from what was LGTM'ed earlier

[reames]

lib/Transforms/IPO/FunctionAttrs.cpp

444 ↗

(On Diff #39445)

What prevents the U from being the callee?

[sanjoy]

lib/Transforms/IPO/FunctionAttrs.cpp

444 ↗

(On Diff #39445)

Since we're exploring transitive uses of an argument, if such a value was a callee the call would be an indirect call; and we'd take the early return on line 431.

I can change the assertion failure message to be more specific if you think that will make things clearer.

[reames]

LGTM

llvm/trunk/lib/Transforms/IPO/FunctionAttrs.cpp

determinePointerReadAttrs(Argument *A,
   for (Use &U : A->uses()) {
     Visited.insert(&U);
     Worklist.push_back(&U);
   }
 
   while (!Worklist.empty()) {
     Use *U = Worklist.pop_back_val();
     Instruction *I = cast<Instruction>(U->getUser());
-    Value *V = U->get();
 
     switch (I->getOpcode()) {
     case Instruction::BitCast:
     case Instruction::GetElementPtr:
     case Instruction::PHI:
     case Instruction::Select:
     case Instruction::AddrSpaceCast:
       // The original value is not read/written via this if the new value isn't.
case Instruction::Invoke: {
         if (CS.onlyReadsMemory()) {
           IsRead = true;
           AddUsersToWorklistIfCapturing();
           continue;
         }
         return Attribute::None;
       }
 
-      Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
-      CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end();
-      for (CallSite::arg_iterator A = B; A != E; ++A, ++AI) {
-        if (A->get() == V) {
-          if (AI == AE) {
-            assert(F->isVarArg() &&
-                   "More params than args in non-varargs call.");
-            return Attribute::None;
-          }
-          Captures &= !CS.doesNotCapture(A - B);
-          if (SCCNodes.count(&*AI))
-            continue;
-          if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(A - B))
-            return Attribute::None;
-          if (!CS.doesNotAccessMemory(A - B))
-            IsRead = true;
-        }
-      }
+      // Note: the callee and the two successor blocks *follow* the argument
+      // operands.  This means there is no need to adjust UseIndex to account
+      // for these.
+
+      unsigned UseIndex = std::distance(CS.arg_begin(), U);
+
+      assert(UseIndex < CS.arg_size() && "Non-argument use?");
+      if (UseIndex >= F->arg_size()) {
+        assert(F->isVarArg() && "More params than args in non-varargs call");
+
+      Captures &= !CS.doesNotCapture(UseIndex);
+      if (!SCCNodes.count(std::next(F->arg_begin(), UseIndex))) {
+        if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(UseIndex))
+        if (!CS.doesNotAccessMemory(UseIndex))
+
       AddUsersToWorklistIfCapturing();
       break;
     }
 
     case Instruction::Load:
       IsRead = true;
       break;
 

llvm/trunk/test/Transforms/FunctionAttrs/out-of-bounds-iterator-bug.ll

+; RUN: opt -functionattrs -S < %s | FileCheck %s
+
+; This checks for an iterator wraparound bug in FunctionAttrs.  The previous
+; "incorrect" behavior was inferring readonly for the %x argument in @caller.
+; Inferring readonly for %x *is* actually correct, since @va_func is marked
+; readonly, but FunctionAttrs was inferring readonly for the wrong reasons (and
+; we _need_ the readonly on @va_func to trigger the problematic code path).  It
+; is possible that in the future FunctionAttrs becomes smart enough to infer
+; readonly for %x for the right reasons, and at that point this test will have
+; to be marked invalid.
+
+declare void @llvm.va_start(i8*)
+declare void @llvm.va_end(i8*)
+
+define void @va_func(i32* readonly %b, ...) readonly nounwind {
+; CHECK-LABEL: define void @va_func(i32* nocapture readonly %b, ...)
+ entry:
+  %valist = alloca i8
+  call void @llvm.va_start(i8* %valist)
+  call void @llvm.va_end(i8* %valist)
+  %x = call i32 @caller(i32* %b)
+  ret void
+}
+
+define i32 @caller(i32* %x) {
+; CHECK-LABEL: define i32 @caller(i32* nocapture %x)
+ entry:
+  call void(i32*,...) @va_func(i32* null, i32 0, i32 0, i32 0, i32* %x)
+  ret i32 42
+}