[FunctionAttrs] Detect printf-like functions and propagate readonly+nocapture to variadic operands

[jmolloy]

Summary

If a function is just a wrapper around vsprintf or friends, in some cases it neither captures nor writes its arguments.

Because such a function is variadic, we are very conservative about any operand it is called with elsewhere in the compiler, so here if we can we should propagate readonly + nocapture to any operand to the function at all callsites.

A variadic pointer argument to a printf-like function is only sometimes nocapture+readonly. For example in this case foo is captured into bar:

sprintf(buf, "%p", &foo); sscanf(buf, "%p", &bar);

For this reason we have to be careful which pointer arguments we mark as nocapture, and we have to parse the format string to be able to understand how the pointer is being used. In this implementation, the only "safe" use of a pointer is "%s", as it is not possible to encode the pointer address textually via %s (unlike with almost any numeric operator: %d/%u/%f etc).

Even though this code only detects %s, it is still useful as %s is so widely used. Consider a "plugin structure":

struct a { const char identifier[32], void (*f)(); } A;
myprintf("ident: %s\n", &A.identifier);

Even if A were determined to be constant, no calls to A.f() could be speculated because a pointer into A is potentially captured. With this analysis we can determine that A is not captured so GlobalOpt can SROA the struct and make indirect calls to A.f() direct.

In the future this can be extended to other v* functions in the standard library that have defined behavior on their operands, such as vscanf and friends (these do not capture, but do write).

[jmolloy]

Ping!

Adding more reviewers - is anyone available to give this a look?

Cheers,

James

[sbaranga]

Hi James,

Do you know what other parts of the compiler are preventing us from figuring out the readonly/nocapture attributes?

If we could use the existing infrastructure for this we might get a more general solution (I'm not saying that's possible).

Cheers,
Silviu

lib/Transforms/IPO/FunctionAttrs.cpp

881

Wouldn't it be enough to have readonly/nocapture? Why do we need to test for library functions?

[sbaranga]

Hi James,

Ok, that makes sense.

So this is a work-around for the lack of attributes for varargs in llvm IR (which affects mostly library functions?).

There might be alternative solutions (either allowing attributes for .. or being able to mark the entire function as nocapture),
but I can’t tell if that would be worth it or not… This is something that might be worth thinking about.

I’ll have to leave this review to someone else, I wouldn’t feel confident enough to give a lgtm in this area.

Cheers,
Silviu

From: James Molloy [mailto:[e-mail]]
Sent: 12 November 2015 16:41
To: [e-mail]; Silviu Baranga; James Molloy; [e-mail]; [e-mail]; [e-mail]; [e-mail]
Cc: [e-mail]
Subject: Re: [PATCH] D14497: [FunctionAttrs] Detect printf-like functions and propagate readnone+nocapture to variadic operands

Hi Silviu,

The problem is that most of the compiler expects function argument attributes to be the same as call operand attributes. Most of FunctionAttrs is devoted to inferring and adding attributes to function arguments (see most of the code below my change, where it finds nocapture). For varargs, there is no such function argument as the number of call operands are greater than the number of function arguments. There's just no representation for "..." to have attributes in the IR.

As to why we check for LibFuncs, that's because it's possible to take a variable argument and do whatever you like with it. You could capture it, store it to a global, write over it... In fact, vscanf() does this exactly and writes into its variable arguments.

James

[majnemer]

If I am not mistaken, these functions may capture the variadic arguments in Glibc environments via register_printf_specifier and register_printf_function. Personally, I'd sleep fine at night if we assumed that registered handler functions cannot capture or store to the arguments.

lib/Transforms/IPO/FunctionAttrs.cpp

910–913

Your description says ReadNone but the code says ReadOnly.

[eli.friedman]

sprintf definitely isn't nocapture; simple testcase:

#include <stdio.h>
#include <assert.h>
int main() {
    int a = 3;
    // Serialize the address of `a`
    char buf[32];
    sprintf(buf, "%p", &a);
    // Deserialize the address of `a`
    int* aptr;
    sscanf(buf, "%p", &aptr);
    // Check value of `a`
    assert(*aptr == 3);
}

sprintf can also write to its arguments: "%n" might not be particularly popular, but it's still legal.

[jmolloy]

Hi David, Eli,

Thanks for looking this over. Eli, thanks for jumping in - you're completely right, and I hadn't considered this.

Going back to the drawing board a little, I think the single most important thing to be able to handle is "%s" specifiers. These are obviously incredibly common and I'd argue are might contribute the most to (non-legitmately) escaping pointers.

The revamped patch adds parsing support for printf-style format strings. The parsing isn't perfect, but it doesn't need to be - a best-effort approach is probably good enough for most cases.

The new patch will only ever add readonly+nocapture to pointer arguments known to be used in %s specifiers. It can be extended if we later find we want to infer attributes on other arguments (perhaps %p/%d/%u can still be readonly, just not nocapture? and %n can be nocapture but not readonly?)

I appreciate it's now significantly more code.

Cheers,

James

[jmolloy]

On second thoughts, this is getting a bit too complex and special-cased. I'll try and find an alternative solution,

lib/Transforms/IPO/FunctionAttrs.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO.h"
 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/StringExtras.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
 
     if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
       return false;
   }
 
   return true;
 }
 
+/// Tests whether a function is "printf-like".
+///
+/// A function is "printf-like" if it uses varargs and the only use of the
+/// variable argument list is to pass to a vsprintf-like function. We know
+/// vsprintf and friends do not capture or write their variadic arguments,
+/// so can propagate readonly+nocapture to all calls of F.
+///
+/// If this is a printf-like function, true is returned and \c FormatStr is
+/// set to the value providing the printf format string.
+static bool isPrintfLikeFunction(Function *F, const TargetLibraryInfo &TLI,
+                                 Value *&FormatStr) {
+  if (!F->isVarArg())
+    return false;
+
+  // We search for a call to @llvm.vastart(i8* %x). If %x isn't an alloca we
+  // bail out.
+  // Then we search for all uses of %x, following through bitcasts. We use a
+  // CaptureTracker to identify uses of %x as call operands, then later check
+  // that the operand is to a call to a known library function such as vsprintf.
+
+  // Find the va_start call.
+  Instruction *VaStartInst = nullptr;
+  for (auto &I : F->getEntryBlock())
+    if (auto *Intr = dyn_cast<IntrinsicInst>(&I))
+      if (Intr->getIntrinsicID() == Intrinsic::vastart) {
+        if (VaStartInst)
+          // Multiple va_starts seen - we only support one.
+          return false;
+        VaStartInst = Intr;
+      }
+  if (!VaStartInst)
+    return false;
+
+  const DataLayout &DL = F->getParent()->getDataLayout();
+  Value *UnderlyingVaStart =
+      GetUnderlyingObject(VaStartInst->getOperand(0), DL);
+
+  if (!isa<AllocaInst>(UnderlyingVaStart))
+    return false;
+  
+  struct ValistCaptureTracker : public CaptureTracker {
+    bool Captured = false;
+    const Use *Call = nullptr;
+
+    ~ValistCaptureTracker() {}
+
+    void tooManyUses() override { Captured = true; }
+
+    bool shouldExplore(const Use *U) override {
+      if (auto *LI = dyn_cast<LoadInst>(U->getUser())) {
+        // The value has been loaded. Is it (only) used in a call?
+        Value *V = LI;
+        // Spool through single-use instructions if needed.
+        while (V->hasOneUse() && !isa<CallInst>(*V->user_begin()))
+          V = *V->user_begin();
+        if (V->hasOneUse() && isa<CallInst>(*V->user_begin())) {
+          if (Call)
+            // Multiple calls seen!
+            Captured = true;
+          else
+            Call = &*V->use_begin();
+        } else {
+          // Loaded value is used in multiple places or not in a call.
+          Captured = true;
+        }
+      }
+
+      return !Captured;
+    }
+    bool captured(const Use *U) override {
+      if (auto *I = dyn_cast<IntrinsicInst>(U->getUser()))
+        if (I->getIntrinsicID() == Intrinsic::vastart ||
+            I->getIntrinsicID() == Intrinsic::vaend)
+          // Not captured, keep going.
+          return false;
+
+      if (Operator::getOpcode(U->getUser()) == Instruction::BitCast)
+        // Not captured, keep going.
+        return false;
+
+      Captured = true;
+      return true;
+    }
+  };
+  ValistCaptureTracker Tracker;
+  PointerMayBeCaptured(UnderlyingVaStart, &Tracker);
+
+  if (Tracker.Captured || !Tracker.Call)
+    return false;
+
+  // Now, is the call to a known va_list function?
+  Function *CalledF =
+      cast<CallInst>(Tracker.Call->getUser())->getCalledFunction();
+  if (!CalledF)
+    return false;
+
+  LibFunc::Func TheLibFunc;
+  if (!(TLI.getLibFunc(CalledF->getName(), TheLibFunc) && TLI.has(TheLibFunc)))
+    return false;
+
+  unsigned FormatArgNo;
+  switch (TheLibFunc) {
+  default:
+    return false;
+  case LibFunc::vprintf:
+    FormatArgNo = 0;
+    break;
+  case LibFunc::vsprintf:
+    FormatArgNo = 1;
+    break;
+  case LibFunc::vfprintf:
+    FormatArgNo = 1;
+    break;
+  case LibFunc::vsnprintf:
+    FormatArgNo = 2;
+    break;
+  }
+  FormatStr =
+      cast<CallInst>(Tracker.Call->getUser())->getArgOperand(FormatArgNo);
+  return true;
+}
+
+/// If \c GV is a constant string, return it as a StringRef otherwise return
+/// an empty string.
+static StringRef getStringFromGV(GlobalVariable *GV) {
+  if (!GV)
+    return StringRef();
+  Constant *C = GV->getInitializer();
+  if (!C || !GV->hasDefinitiveInitializer())
+    return StringRef();
+  if (auto *CDS = dyn_cast<ConstantDataSequential>(C))
+    if (CDS->isString())
+      return CDS->getAsString();
+  return StringRef();
+}
+
+/// \c &S[I] is a printf modifer-specifier sequence, for example "08s". Skip
+/// over the modifiers ('0' and '2' in this example) and return the index of the
+/// specifier ('s' in this example).
+///
+/// Return ~0U on failure.
+static unsigned getPrintfSpecifierCharSkippingModifiers(StringRef S,
+                                                        unsigned I) {
+  for (unsigned E = S.size(); I != E; ++I) {
+    switch (S[I]) {
+    case '0': case '1': case '2': case '3': case '4':
+    case '5': case '6': case '7': case '8': case '9':
+    case ' ':
+      continue;
+    default:
+      return I;
+    }
+  }
+  return ~0U;
+}
+
+/// \c FormatStrVal is a Value providing a printf format string during the call
+/// \c CI. Try and resolve the Value to a StringRef, parse it, and return the
+/// format specifiers.
+///
+/// For example, given @g = constant c"a: %s, %02d", it would return {'s', 'd'}.
+///
+/// On failure return an empty list.
+static SmallVector<char, 4> resolvePrintfFormatStr(Value *FormatStrVal,
+                                                   CallInst *CI) {
+  SmallVector<char, 4> V;
+  if (!FormatStrVal)
+    return V;
+  FormatStrVal = FormatStrVal->stripPointerCasts();
+
+  // We support FormatStrVal coming directly from a constant global, or coming
+  // from an operand to CI, which itself is a constant global.
+
+  StringRef Str;
+  if (auto *GV = dyn_cast<GlobalVariable>(FormatStrVal)) {
+    Str = getStringFromGV(GV);
+  } else if (auto *A = dyn_cast<Argument>(FormatStrVal)) {
+    auto *Op = std::next(CI->op_begin(), A->getArgNo())->get();
+    Str = getStringFromGV(dyn_cast<GlobalVariable>(Op->stripPointerCasts()));
+  }
+
+  // Process the format string, extracting known specifiers and ignoring
+  // modifiers.
+  for (unsigned I = 0, E = Str.size(); I < E; ++I) {
+    if (Str[I] != '%')
+      continue;
+    // Skip over '%'.
+    ++I;
+    if (Str[I] == '%')
+      // Escape.
+      continue;
+
+    // This doesn't have to be 100% accurate. As long as it knows enough about
+    // format modifiers to catch the obvious/standard cases, that is good
+    // enough.
+    I = getPrintfSpecifierCharSkippingModifiers(Str, I);
+    if (I == ~0U)
+      return SmallVector<char,4>();
+    
+    switch (Str[I]) {
+    default:
+      // Unrecognized format specifier - abort completely.
+      return SmallVector<char,4>();
+    case 's': case 'd': case 'u': case 'f': case 'F': case 'p':
+    case 'g': case 'G': case 'a': case 'A': case 'e': case 'E':
+    case 'x': case 'X': case 'o': case 'i': case 'c':
+      V.push_back(Str[I]);
+      break;
+    }
+  }
+  return V;
+}
+
+/// Return the attributes inferrable for this parameter due to \c Specifier.
+/// The only specifier implemented currently is '%s', which implies nocapture
+/// and readonly.
+static AttributeSet getAttributesForPrintfSpecifier(char Specifier,
+                                                    unsigned ParamIdx,
+                                                    LLVMContext &C) {
+  AttributeSet AS;
+  if (Specifier != 's')
+    return AS;
+  AS = AS.addAttribute(C, ParamIdx, Attribute::NoCapture);
+  AS = AS.addAttribute(C, ParamIdx, Attribute::ReadOnly);
+  return AS;
+}
+
+// Deduce attributes for variadic arguments in the SCC.
+static bool addVarArgAttrs(const SCCNodeSet &SCCNodes,
+                           const TargetLibraryInfo &TLI) {
+  // Look for functions whose variadic arguments only flow to libcalls known
+  // not to capture or write them, and add nocapture+readonly to their
+  // callsites where applicable.
+  //
+  // This applies to any pointer type variadic operand. Unfortunately many
+  // printf format specifiers can actually capture the pointer; e.g.
+  //
+  //   sprintf(buf, "%p", &foo); sscanf(buf, "%p", &bar);
+  //
+  // And some can actually write to their operands;
+  //
+  //   sprintf(bug, "%n", &foo);
+  //
+  // So here we only handle a specific format specifier - "%s". %s is one
+  // of the most used format specifiers and takes a pointer argument
+  // but does not serialize the pointer value itself.
+  //
+  // Knowing that a string does not get written or get captured can be useful
+  // for such things as performing SROA on an aggregate:
+  //
+  //   struct a { const char str[32], void (*f)() } A = ...;
+  //   my_printf("xyz: %s\n", &a.str);
+  //
+  // Without knowing that &a.str is nocapture and readonly, we would never be
+  // able to devirtualize calls to a.f(), even if "A" was determined to be
+  // constant.
+  //
+  // FIXME: This can be extended to work for vscanf and friends, adding
+  // nocapture (but not readonly).
+  bool Changed = false;
+  for (Function *F : SCCNodes) {
+    if (F->isDeclaration() || F->mayBeOverridden() || !F->isVarArg())
+      continue;
+
+    // "isPrintfLikeFunction()" can possibly be expensive. Do an early exit
+    // check: does the function even have any (variadic) pointer operands?
+    unsigned NumNonVarArgs = F->getFunctionType()->getNumParams();
+    bool HasPointerArg = false;
+    for (auto *U : F->users())
+      if (CallInst *CI = dyn_cast<CallInst>(U))
+        for (unsigned I = NumNonVarArgs; I < CI->getNumArgOperands(); ++I)
+          if (CI->getArgOperand(I)->getType()->isPointerTy()) {
+            HasPointerArg = true;
+            break;
+          }
+    if (!HasPointerArg)
+      continue;
+    
+    Value *FormatStrVal = nullptr;
+    if (!isPrintfLikeFunction(F, TLI, FormatStrVal) || !FormatStrVal)
+      continue;
+
+    LLVMContext &C = F->getContext();
+    for (auto *U : F->users())
+      if (CallInst *CI = dyn_cast<CallInst>(U)) {
+        SmallVector<char, 4> Format = resolvePrintfFormatStr(FormatStrVal, CI);
+        for (unsigned I = NumNonVarArgs, J = 0; I < CI->getNumArgOperands();
+             ++I, ++J)
+          if (CI->getArgOperand(I)->getType()->isPointerTy() &&
+              J < Format.size()) {
+            AttributeSet AddAttrs =
+                getAttributesForPrintfSpecifier(Format[J], I + 1, C);
+            if (AddAttrs.isEmpty())
+              continue;
+            AttributeSet Attrs = CI->getAttributes();
+            Attrs = Attrs.addAttributes(C, I + 1, AddAttrs);
+            if (Attrs != CI->getAttributes())
+              Changed = true;
+            CI->setAttributes(Attrs);
+          }
+      }
+  }
+  return Changed;
+}
+
 /// Deduce noalias attributes for the SCC.
 static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) {
   // Check each function in turn, determining which functions return noalias
   // pointers.
   for (Function *F : SCCNodes) {
     // Already noalias.
     if (F->doesNotAlias(0))
       continue;
bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
   Changed |= addArgumentAttrs(SCCNodes);
 
   // If we have no external nodes participating in the SCC, we can infer some
   // more precise attributes as well.
   if (!ExternalNode) {
     Changed |= addNoAliasAttrs(SCCNodes);
     Changed |= addNonNullAttrs(SCCNodes, *TLI);
   }
-  
+  Changed |= addVarArgAttrs(SCCNodes, *TLI);
   Changed |= addNoRecurseAttrs(SCC, Revisit);
   return Changed;
 }
 
 bool FunctionAttrs::doFinalization(CallGraph &CG) {
   bool Changed = false;
   // When iterating over SCCs we visit functions in a bottom-up fashion. Some of
   // the rules we have for identifying norecurse functions work best with a
   // top-down walk, so look again at all the functions we previously marked as
   // worth revisiting, in top-down order.
   for (auto &F : reverse(Revisit))
     if (F)
       Changed |= addNoRecurseAttrsTopDownOnly(cast<Function>((Value*)F));
   return Changed;
 }

test/Transforms/FunctionAttrs/varargs.ll

+; RUN: opt < %s -functionattrs -S | FileCheck %s
+
+target triple = "armv7--linux-gnueabihf"
+
+%struct.__va_list = type { i8* }
+
+declare i32 @vsprintf(i8* readonly nocapture, i8* readonly nocapture, [1 x i32])
+
+; @f() is "printf-like", so any varargs operands to it should be readonly+nocapture.
+define i32 @f(i8* nocapture %a, i8* nocapture readonly %b, ...) #0 {
+  %v = alloca %struct.__va_list, align 4
+  %1 = bitcast %struct.__va_list* %v to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %1)
+  call void @llvm.va_start(i8* %1)
+  %2 = bitcast %struct.__va_list* %v to i32*
+  %3 = load i32, i32* %2, align 4
+  %4 = insertvalue [1 x i32] undef, i32 %3, 0
+  %5 = call arm_aapcscc i32 @vsprintf(i8* %a, i8* %b, [1 x i32] %4) #1
+  call void @llvm.va_end(i8* %1)
+  call void @llvm.lifetime.end(i64 4, i8* %1)
+  ret i32 %5
+}
+
+; CHECK-LABEL: @percent_s
+; CHECK: call i32 (i8*, i8*, ...) @f(i8* %a, i8* {{.*}}, i8* nocapture readonly %c, i32 %d)
+define i32 @percent_s(i8* %a, i8* %b, i8* %c, i32 %d) {
+  %x = call i32 (i8*,i8*, ...) @f(i8* %a, i8* bitcast ([8 x i8]* @b to i8*), i8* %c, i32 %d)
+  ret i32 %x
+}
+
+; This function uses %d, which can serialize a pointer.
+; CHECK-LABEL: @percent_d
+; CHECK: call i32 (i8*, i8*, ...) @f(i8* %a, i8* {{.*}}, i8* %c, i32 %d)
+define i32 @percent_d(i8* %a, i8* %b, i8* %c, i32 %d) {
+  %x = call i32 (i8*,i8*, ...) @f(i8* %a, i8* bitcast ([8 x i8]* @c to i8*), i8* %c, i32 %d)
+  ret i32 %x
+}
+
+; This function uses %p, which can serialize a pointer. It also has a percent-escape (%%)
+; in it, so check it doesn't get confused.
+; CHECK-LABEL: @percent_p
+; CHECK: call i32 (i8*, i8*, ...) @f(i8* %a, i8* {{.*}}, i8* %c, i8* nocapture readonly %d)
+define i32 @percent_p(i8* %a, i8* %b, i8* %c, i8* %d) {
+  %x = call i32 (i8*,i8*, ...) @f(i8* %a, i8* bitcast ([11 x i8]* @d to i8*), i8* %c, i8* %d)
+  ret i32 %x
+}
+
+; CHECK-LABEL: @percent_s_mod
+; CHECK: call i32 (i8*, i8*, ...) @f(i8* %a, i8* {{.*}}, i8* %c, i8* nocapture readonly %d)
+define i32 @percent_s_mod(i8* %a, i8* %b, i8* %c, i8* %d) {
+  %x = call i32 (i8*,i8*, ...) @f(i8* %a, i8* bitcast ([11 x i8]* @e to i8*), i8* %c, i8* %d)
+  ret i32 %x
+}
+
+@b = constant [8 x i8] c"a: %s %d"
+@c = constant [8 x i8] c"a: %d %d"
+@d = constant [11 x i8] c"a: %% %d %s"
+@e = constant [11 x i8] c"a: %0d % 2s"
+
+declare void @llvm.lifetime.start(i64, i8* nocapture)
+declare void @llvm.lifetime.end(i64, i8* nocapture)
+declare void @llvm.va_start(i8*)
+declare void @llvm.va_end(i8*)