Update optimization passes to handle inalloca arguments

[rnk]

Summary

I searched Transforms/ and Analysis/ for 'ByVal' and updated those call
sites to check for inalloca if appropriate.

I added tests for any change that would allow an optimization to fire on
inalloca.

[nlewycky]

include/llvm/IR/Argument.h

64 ↗

(On Diff #6203)

"the byval attribute or inalloca attribute"
or *the inalloca attribute?

"from the perspective of the callee" doesn't really tell the reader much (why are they similar?). Suggestion: "These attributes both represent arguments being passed by copy under different ABIs."

include/llvm/IR/Instructions.h

35 ↗

(On Diff #6203)

Sort.

115 ↗

(On Diff #6203)

Unclear what "static" means here.

120 ↗

(On Diff #6203)

Optional: Why do you need isUsedWithInAlloca() instead of just calling this and testing the result? CallSite evaluates to false when zero-initialized.

lib/IR/Instructions.cpp

935 ↗

(On Diff #6203)

No action required: By the way, this is actually O(n^2) not O(n) because attributes are stored in a linked list so finding 1+ArgNo is not constant time. See PR16536.

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

84 ↗

(On Diff #6203)

"considered to be" --> "implicitly"? You get undef if you load from one afterwards, right?

[rnk]

Rebase everything on top of redesigned inalloca

[rnk]

A lot of this changed and I think the questionable parts went away. PTAL

include/llvm/IR/Argument.h

64 ↗

(On Diff #6203)

Done.

include/llvm/IR/Instructions.h

35 ↗

(On Diff #6203)

Gone.

115 ↗

(On Diff #6203)

It's unclear immediately after "isStaticAlloca()?"

120 ↗

(On Diff #6203)

Gone now, but I thought it read better.

lib/IR/Instructions.cpp

935 ↗

(On Diff #6203)

Interesting. This code is gone now. =/

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

84 ↗

(On Diff #6203)

Or just "are clobbered..."

[rnk]

Revert CallSite.h change

[rnk]

• tweak comments and add a test case.

[nlewycky]

Please merge test/Transforms/ArgumentPromotion/inalloca.ll and test/Transforms/ArgumentPromotion/inalloca-2.ll

[rnk]

Done. Thanks!

[rnk]

Closed by commit rL200281 (authored by @rnk).

llvm/trunk/lib/Analysis/MemoryBuiltins.cpp

if (const ConstantInt *C = dyn_cast<ConstantInt>(ArraySize)) {
     Size *= C->getValue().zextOrSelf(IntTyBits);
     return std::make_pair(align(Size, I.getAlignment()), Zero);
   }
   return unknown();
 }
 
 SizeOffsetType ObjectSizeOffsetVisitor::visitArgument(Argument &A) {
   // no interprocedural analysis is done at the moment
-  if (!A.hasByValAttr()) {
+  if (!A.hasByValOrInAllocaAttr()) {
     ++ObjectVisitorArgument;
     return unknown();
   }
   PointerType *PT = cast<PointerType>(A.getType());
   APInt Size(IntTyBits, DL->getTypeAllocSize(PT->getElementType()));
   return std::make_pair(align(Size, A.getParamAlignment()), Zero);
 }
 

llvm/trunk/lib/Analysis/ValueTracking.cpp

if (GA->mayBeOverridden()) {
       ComputeMaskedBits(GA->getAliasee(), KnownZero, KnownOne, TD, Depth+1);
     }
     return;
   }
 
   if (Argument *A = dyn_cast<Argument>(V)) {
     unsigned Align = 0;
 
-    if (A->hasByValAttr()) {
-      // Get alignment information off byval arguments if specified in the IR.
+    if (A->hasByValOrInAllocaAttr()) {
+      // Get alignment information off byval/inalloca arguments if specified in
+      // the IR.
       Align = A->getParamAlignment();
     } else if (TD && A->hasStructRetAttr()) {
       // An sret parameter has at least the ABI alignment of the return type.
       Type *EltTy = cast<PointerType>(A->getType())->getElementType();
       if (EltTy->isSized())
         Align = TD->getABITypeAlignment(EltTy);
     }
 

 }
 
 /// isKnownNonNull - Return true if we know that the specified value is never
 /// null.
 bool llvm::isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI) {
   // Alloca never returns null, malloc might.
   if (isa<AllocaInst>(V)) return true;
 
-  // A byval argument is never null.
+  // A byval or inalloca argument is never null.
   if (const Argument *A = dyn_cast<Argument>(V))
-    return A->hasByValAttr();
+    return A->hasByValOrInAllocaAttr();
 
   // Global values are not null unless extern weak.
   if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
     return !GV->hasExternalWeakLinkage();
 
   // operator new never returns null.
   if (isOperatorNewLikeFn(V, TLI, /*LookThroughBitCast=*/true))
     return true;
 
   return false;
 }

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

CallGraphNode *ArgPromotion::PromoteArguments(CallGraphNode *CGN) {
   // add it to ArgsToPromote.
   SmallPtrSet<Argument*, 8> ArgsToPromote;
   SmallPtrSet<Argument*, 8> ByValArgsToTransform;
   for (unsigned i = 0, e = PointerArgs.size(); i != e; ++i) {
     Argument *PtrArg = PointerArgs[i];
     Type *AgTy = cast<PointerType>(PtrArg->getType())->getElementType();
 
     // If this is a byval argument, and if the aggregate type is small, just
-    // pass the elements, which is always safe.
+    // pass the elements, which is always safe.  This does not apply to
+    // inalloca.
     if (PtrArg->hasByValAttr()) {
       if (StructType *STy = dyn_cast<StructType>(AgTy)) {
         if (maxElements > 0 && STy->getNumElements() > maxElements) {
           DEBUG(dbgs() << "argpromotion disable promoting argument '"
                 << PtrArg->getName() << "' because it would require adding more"
                 << " than " << maxElements << " arguments to the function.\n");
           continue;
         }
if (isSelfRecursive) {
           }
         }
         if (RecursiveType)
           continue;
       }
     }
     
     // Otherwise, see if we can promote the pointer to its value.
-    if (isSafeToPromoteArgument(PtrArg, PtrArg->hasByValAttr()))
+    if (isSafeToPromoteArgument(PtrArg, PtrArg->hasByValOrInAllocaAttr()))
       ArgsToPromote.insert(PtrArg);
   }
 
   // No promotable pointer arguments.
   if (ArgsToPromote.empty() && ByValArgsToTransform.empty()) 
     return 0;
 
   return DoPromotion(F, ArgsToPromote, ByValArgsToTransform);
static void MarkIndicesSafe(const ArgPromotion::IndicesVector &ToMark,
   }
 }
 
 /// isSafeToPromoteArgument - As you might guess from the name of this method,
 /// it checks to see if it is both safe and useful to promote the argument.
 /// This method limits promotion of aggregates to only promote up to three
 /// elements of the aggregate in order to avoid exploding the number of
 /// arguments passed in.
-bool ArgPromotion::isSafeToPromoteArgument(Argument *Arg, bool isByVal) const {
+bool ArgPromotion::isSafeToPromoteArgument(Argument *Arg,
+                                           bool isByValOrInAlloca) const {
   typedef std::set<IndicesVector> GEPIndicesSet;
 
   // Quick exit for unused arguments
   if (Arg->use_empty())
     return true;
 
   // We can only promote this argument if all of the uses are loads, or are GEP
   // instructions (with constant indices) that are subsequently loaded.
   //
   // Promoting the argument causes it to be loaded in the caller
   // unconditionally. This is only safe if we can prove that either the load
   // would have happened in the callee anyway (ie, there is a load in the entry
   // block) or the pointer passed in at every call site is guaranteed to be
   // valid.
   // In the former case, invalid loads can happen, but would have happened
   // anyway, in the latter case, invalid loads won't happen. This prevents us
   // from introducing an invalid load that wouldn't have happened in the
   // original code.
   //
   // This set will contain all sets of indices that are loaded in the entry
   // block, and thus are safe to unconditionally load in the caller.
+  //
+  // This optimization is also safe for InAlloca parameters, because it verifies
+  // that the address isn't captured.
   GEPIndicesSet SafeToUnconditionallyLoad;
 
   // This set contains all the sets of indices that we are planning to promote.
   // This makes it possible to limit the number of arguments added.
   GEPIndicesSet ToPromote;
 
   // If the pointer is always valid, any load with first index 0 is valid.
-  if (isByVal || AllCallersPassInValidPointerForArgument(Arg))
+  if (isByValOrInAlloca || AllCallersPassInValidPointerForArgument(Arg))
     SafeToUnconditionallyLoad.insert(IndicesVector(1, 0));
 
   // First, iterate the entry block and mark loads of (geps of) arguments as
   // safe.
   BasicBlock *EntryBlock = Arg->getParent()->begin();
   // Declare this here so we can reuse it
   IndicesVector Indices;
   for (BasicBlock::iterator I = EntryBlock->begin(), E = EntryBlock->end();
if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
       if (GEP->use_empty()) {
         // Dead GEP's cause trouble later.  Just remove them if we run into
         // them.
         getAnalysis<AliasAnalysis>().deleteValue(GEP);
         GEP->eraseFromParent();
         // TODO: This runs the above loop over and over again for dead GEPs
         // Couldn't we just do increment the UI iterator earlier and erase the
         // use?
-        return isSafeToPromoteArgument(Arg, isByVal);
+        return isSafeToPromoteArgument(Arg, isByValOrInAlloca);
       }
 
       // Ensure that all of the indices are constants.
       for (User::op_iterator i = GEP->idx_begin(), e = GEP->idx_end();
         i != e; ++i)
         if (ConstantInt *C = dyn_cast<ConstantInt>(*i))
           Operands.push_back(C->getSExtValue());
         else

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

bool DAE::RemoveDeadArgumentsFromCallers(Function &Fn)
   if (Fn.use_empty())
     return false;
 
   SmallVector<unsigned, 8> UnusedArgs;
   for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(); 
        I != E; ++I) {
     Argument *Arg = I;
 
-    if (Arg->use_empty() && !Arg->hasByValAttr())
+    if (Arg->use_empty() && !Arg->hasByValOrInAllocaAttr())
       UnusedArgs.push_back(Arg->getArgNo());
   }
 
   if (UnusedArgs.empty())
     return false;
 
   bool Changed = false;
 

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

 static Attribute::AttrKind
 determinePointerReadAttrs(Argument *A,
                           const SmallPtrSet<Argument*, 8> &SCCNodes) {
                                                        
   SmallVector<Use*, 32> Worklist;
   SmallSet<Use*, 32> Visited;
   int Count = 0;
 
+  // inalloca arguments are always clobbered by the call.
+  if (A->hasInAllocaAttr())
+    return Attribute::None;
+
   bool IsRead = false;
   // We don't need to track IsWritten. If A is written to, return immediately.
 
   for (Value::use_iterator UI = A->use_begin(), UE = A->use_end();
        UI != UE; ++UI) {
     if (Count++ >= 20)
       return Attribute::None;
 

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

bool IPCP::PropagateConstantsIntoArguments(Function &F) {
 
   // If we got to this point, there is a constant argument!
   assert(NumNonconstant != ArgumentConstants.size());
   bool MadeChange = false;
   Function::arg_iterator AI = F.arg_begin();
   for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) {
     // Do we have a constant argument?
     if (ArgumentConstants[i].second || AI->use_empty() ||
-        (AI->hasByValAttr() && !F.onlyReadsMemory()))
+        AI->hasInAllocaAttr() || (AI->hasByValAttr() && !F.onlyReadsMemory()))
       continue;
   
     Value *V = ArgumentConstants[i].first;
     if (V == 0) V = UndefValue::get(AI->getType());
     AI->replaceAllUsesWith(V);
     ++NumArgumentsProped;
     MadeChange = true;
   }

llvm/trunk/lib/Transforms/InstCombine/InstCombineCalls.cpp

 /// passed through the varargs area, we can eliminate the use of the cast.
 static bool isSafeToEliminateVarargsCast(const CallSite CS,
                                          const CastInst * const CI,
                                          const DataLayout * const TD,
                                          const int ix) {
   if (!CI->isLosslessCast())
     return false;
 
-  // The size of ByVal arguments is derived from the type, so we
+  // The size of ByVal or InAlloca arguments is derived from the type, so we
   // can't change to a type with a different size.  If the size were
   // passed explicitly we could avoid this check.
-  if (!CS.isByValArgument(ix))
+  if (!CS.isByValOrInAllocaArgument(ix))
     return true;
 
   Type* SrcTy =
             cast<PointerType>(CI->getOperand(0)->getType())->getElementType();
   Type* DstTy = cast<PointerType>(CI->getType())->getElementType();
   if (!SrcTy->isSized() || !DstTy->isSized())
     return false;
   if (!TD || TD->getTypeAllocSize(SrcTy) != TD->getTypeAllocSize(DstTy))
for (unsigned i = 0, e = NumCommonArgs; i != e; ++i, ++AI) {
     if (!CastInst::isBitCastable(ActTy, ParamTy))
       return false;   // Cannot transform this parameter value.
 
     if (AttrBuilder(CallerPAL.getParamAttributes(i + 1), i + 1).
           hasAttributes(AttributeFuncs::
                         typeIncompatible(ParamTy, i + 1), i + 1))
       return false;   // Attribute not compatible with transformed value.
 
+    if (CS.isInAllocaArgument(i))
+      return false;   // Cannot transform to and from inalloca.
+
     // If the parameter is passed as a byval argument, then we have to have a
     // sized type and the sized type has to have the same size as the old type.
     if (ParamTy != ActTy &&
         CallerPAL.getParamAttributes(i + 1).hasAttribute(i + 1,
                                                          Attribute::ByVal)) {
       PointerType *ParamPTy = dyn_cast<PointerType>(ParamTy);
       if (ParamPTy == 0 || !ParamPTy->getElementType()->isSized() || TD == 0)
         return false;

llvm/trunk/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) {
     }
 
     if (CallSite CS = U) {
       // If this is the function being called then we treat it like a load and
       // ignore it.
       if (CS.isCallee(UI))
         continue;
 
+      // Inalloca arguments are clobbered by the call.
+      unsigned ArgNo = CS.getArgumentNo(UI);
+      if (CS.isInAllocaArgument(ArgNo))
+        return false;
+
       // If this is a readonly/readnone call site, then we know it is just a
       // load (but one that potentially returns the value itself), so we can
       // ignore it if we know that the value isn't captured.
-      unsigned ArgNo = CS.getArgumentNo(UI);
       if (CS.onlyReadsMemory() &&
           (CS.getInstruction()->use_empty() || CS.doesNotCapture(ArgNo)))
         continue;
 
       // If this is being passed as a byval argument, the caller is making a
       // copy, so it is only a read of the alloca.
       if (CS.isByValArgument(ArgNo))
         continue;

llvm/trunk/lib/Transforms/ObjCARC/ObjCARC.h

 static inline bool IsPotentialRetainableObjPtr(const Value *Op) {
   // Pointers to static or stack storage are not valid retainable object
   // pointers.
   if (isa<Constant>(Op) || isa<AllocaInst>(Op))
     return false;
   // Special arguments can not be a valid retainable object pointer.
   if (const Argument *Arg = dyn_cast<Argument>(Op))
     if (Arg->hasByValAttr() ||
+        Arg->hasInAllocaAttr() ||
         Arg->hasNestAttr() ||
         Arg->hasStructRetAttr())
       return false;
   // Only consider values with pointer types.
   //
   // It seemes intuitive to exclude function pointer types as well, since
   // functions are never retainable object pointers, however clang occasionally
   // bitcasts retainable object pointers to function-pointer type temporarily.

llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp

static OverwriteResult isOverwrite(const AliasAnalysis::Location &Later,
   // Otherwise, we have to have size information, and the later store has to be
   // larger than the earlier one.
   if (Later.Size == AliasAnalysis::UnknownSize ||
       Earlier.Size == AliasAnalysis::UnknownSize ||
       AA.getDataLayout() == 0)
     return OverwriteUnknown;
 
   // Check to see if the later store is to the entire object (either a global,
-  // an alloca, or a byval argument).  If so, then it clearly overwrites any
-  // other store to the same object.
+  // an alloca, or a byval/inalloca argument).  If so, then it clearly
+  // overwrites any other store to the same object.
   const DataLayout *TD = AA.getDataLayout();
 
   const Value *UO1 = GetUnderlyingObject(P1, TD),
               *UO2 = GetUnderlyingObject(P2, TD);
 
   // If we can't resolve the same pointers to the same object, then we can't
   // analyze them at all.
   if (UO1 != UO2)
if (isa<AllocaInst>(I))
       DeadStackObjects.insert(I);
 
     // Okay, so these are dead heap objects, but if the pointer never escapes
     // then it's leaked by this function anyways.
     else if (isAllocLikeFn(I, TLI) && !PointerMayBeCaptured(I, true, true))
       DeadStackObjects.insert(I);
   }
 
-  // Treat byval arguments the same, stores to them are dead at the end of the
-  // function.
+  // Treat byval or inalloca arguments the same, stores to them are dead at the
+  // end of the function.
   for (Function::arg_iterator AI = BB.getParent()->arg_begin(),
        AE = BB.getParent()->arg_end(); AI != AE; ++AI)
-    if (AI->hasByValAttr())
+    if (AI->hasByValOrInAllocaAttr())
       DeadStackObjects.insert(AI);
 
   // Scan the basic block backwards
   for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
     --BBI;
 
     // If we find a store, check to see if it points into a dead stack value.
     if (hasMemoryWrite(BBI, TLI) && isRemovable(BBI)) {

llvm/trunk/test/Transforms/ArgumentPromotion/inalloca.ll

+; RUN: opt %s -argpromotion -scalarrepl -S | FileCheck %s
+
+target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128"
+
+%struct.ss = type { i32, i32 }
+
+; Argpromote + scalarrepl should change this to passing the two integers by value.
+define internal i32 @f(%struct.ss* inalloca  %s) {
+entry:
+  %f0 = getelementptr %struct.ss* %s, i32 0, i32 0
+  %f1 = getelementptr %struct.ss* %s, i32 0, i32 1
+  %a = load i32* %f0, align 4
+  %b = load i32* %f1, align 4
+  %r = add i32 %a, %b
+  ret i32 %r
+}
+; CHECK-LABEL: define internal i32 @f
+; CHECK-NOT: load
+; CHECK: ret
+
+define i32 @main() {
+entry:
+  %S = alloca %struct.ss
+  %f0 = getelementptr %struct.ss* %S, i32 0, i32 0
+  %f1 = getelementptr %struct.ss* %S, i32 0, i32 1
+  store i32 1, i32* %f0, align 4
+  store i32 2, i32* %f1, align 4
+  %r = call i32 @f(%struct.ss* inalloca %S)
+  ret i32 %r
+}
+; CHECK-LABEL: define i32 @main
+; CHECK-NOT: load
+; CHECK: ret
+
+; Argpromote can't promote %a because of the icmp use.
+define internal i1 @g(%struct.ss* %a, %struct.ss* inalloca %b) nounwind  {
+; CHECK: define internal i1 @g(%struct.ss* %a, %struct.ss* inalloca %b)
+entry:
+  %c = icmp eq %struct.ss* %a, %b
+  ret i1 %c
+}
+
+define i32 @test() {
+entry:
+  %S = alloca %struct.ss
+  %c = call i1 @g(%struct.ss* %S, %struct.ss* inalloca %S)
+; CHECK: call i1 @g(%struct.ss* %S, %struct.ss* inalloca %S)
+  ret i32 0
+}

llvm/trunk/test/Transforms/DeadStoreElimination/simple.ll

 define void @test9(%struct.x* byval  %a) nounwind  {
   %tmp2 = getelementptr %struct.x* %a, i32 0, i32 0
   store i32 1, i32* %tmp2, align 4
   ret void
 ; CHECK-LABEL: @test9(
 ; CHECK-NEXT: ret void
 }
 
+; Test for inalloca handling.
+define void @test9_2(%struct.x* inalloca  %a) nounwind  {
+  %tmp2 = getelementptr %struct.x* %a, i32 0, i32 0
+  store i32 1, i32* %tmp2, align 4
+  ret void
+; CHECK-LABEL: @test9_2(
+; CHECK-NEXT: ret void
+}
+
 ; va_arg has fuzzy dependence, the store shouldn't be zapped.
 define double @test10(i8* %X) {
         %X_addr = alloca i8*
         store i8* %X, i8** %X_addr
         %tmp.0 = va_arg i8** %X_addr, double
         ret double %tmp.0
 ; CHECK-LABEL: @test10(
 ; CHECK: store

llvm/trunk/test/Transforms/FunctionAttrs/readattrs.ll

 declare void @test6_1()
 ; CHECK: define void @test6_2(i8** nocapture %p, i8* %q)
 ; This is not a missed optz'n.
 define void @test6_2(i8** %p, i8* %q) {
   store i8* %q, i8** %p
   call void @test6_1()
   ret void
 }
+
+; CHECK: define void @test7_1(i32* inalloca nocapture %a)
+; inalloca parameters are always considered written
+define void @test7_1(i32* inalloca %a) {
+  ret void
+}

llvm/trunk/test/Transforms/InstCombine/call-cast-target-inalloca.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+target datalayout = "e-p:32:32"
+target triple = "i686-pc-linux-gnu"
+
+declare void @takes_i32(i32)
+declare void @takes_i32_inalloca(i32* inalloca)
+
+define void @f() {
+; CHECK-LABEL: define void @f()
+  %args = alloca i32
+  call void bitcast (void (i32)* @takes_i32 to void (i32*)*)(i32* inalloca %args)
+; CHECK: call void bitcast
+  ret void
+}
+
+define void @g() {
+; CHECK-LABEL: define void @g()
+  call void bitcast (void (i32*)* @takes_i32_inalloca to void (i32)*)(i32 0)
+; CHECK: call void bitcast
+  ret void
+}