[ArgPromotion] Make a non-byval promotion attempt first

[psamolysov]

Summary

It makes sense to make a non-byval promotion attempt first and then fall
back to the byval one. The non-byval ('usual') promotion is generally
better, for example it does promotion even when a structure has more
elements than 'MaxElements' but not all of them are actually used in the
function.

[psamolysov]

Change the test to use the legacy pass manager, unfortunately the buildbot doesn't accept tests with arguments for the opt tool in the following format: -passes=function(sroa),cgscc(argpromotion).

[psamolysov]

Failed Tests (2):
  LLVM :: DebugInfo/NVPTX/debug-file-loc-only.ll
  LLVM :: DebugInfo/NVPTX/debug-file-loc.ll

These tests look like unrelated to the changes.

[nikic]

Might make sense to move the non-byval promotion attempt first and then fall back to byval? I think non-byval promotion is generally better if it's possible.

Though it would probably make sense to handle byval promotion in the same way as non-byval promotion (but allowing stores) -- I believe the current byval implementation is not correct under opaque pointers.

[psamolysov]

Might make sense to move the non-byval promotion attempt first and then fall back to byval? I think non-byval promotion is generally better if it's possible.

Let's start from this change. I'm going to update the patch moving the non-byval attempt first.

[psamolysov]

Make an attempt to do non-byval promotion first.

[nikic]

llvm/lib/Transforms/IPO/ArgumentPromotion.cpp

857

This std::transform makes the code both longer and harder to read.

[psamolysov]

I've updated the tests to forbid non-byval promotion and let byval chance to work. As I see, not only 'store' is allowed for byval (but not every 'store', for not-densely packed structures, with x86_fp80, for example, stores makes 'canPaddingBeAccessed' to return 'true') but GEPs with non constant indexes too. I think there could be other instructions that is allowed for byval but not allowed for 'usual' promoting, in fact, if isDenselyPacked returns 'true', any user is possible: store, cmp, etc. because byval promotion just replaces passing a structure by value with passing it's elements without care about how they are used if the structure is densely packed or a GEP with non-const index is the only user.

By the way, should GEP with non constant index be a flag that padding can be accessed and in this case the canPaddingBeAccessed function should return 'true'?

[nikic]

@psamolysov Right, byval promotion currently doesn't look at how the argument is used -- however, the promotion will only actually be profitable if the introduced alloca can be mem2reg promoted. This will happen if the argument is only used in load/store operations at constant offset, but will generally not happen in other cases, in which case we've just made argument passing less efficient for no real benefit.

[psamolysov]

@nikic Thank you for the explanation, I think the IsSafeToPromote variable should be used as a flag whether using the argument in stores is allowed and taking into account within the findArgParts function. That refactoring is much larger than the proposed here, so it deserves another review.

llvm/lib/Transforms/IPO/ArgumentPromotion.cpp

857

True, I've returned the loop back.

[psamolysov]

Use the loop to add types into the Types vector for the areTypesABICompatible call instead of the std::transform algorithm.

[nikic]

LGTM

[aeubanks]

In D124514#3476973, @psamolysov wrote:

Change the test to use the legacy pass manager, unfortunately the buildbot doesn't accept tests with arguments for the opt tool in the following format: -passes=function(sroa),cgscc(argpromotion).

this should work if you add quotes, like -passes='function(sroa),cgscc(argpromotion)'

but is there a reason we're not using the output of -passes=sroa as the input IR and only running argpromotion rather than running the test through both sroa and argpromotion?

[psamolysov]

@aeubanks Hm... thank you for the explanation why my first attempt to run two passes didn't work. I used two passes instead of just run argpromotion on an optimized IR because I saw examples of such approach in the tests, llvm\test\Transforms\ArgumentPromotion\2008-09-07-CGUpdate.ll for example runs inline before argpromotion. I've updated the test to run the argpromotion pass only.

[psamolysov]

Update the byval-through-pointer-promotion.ll test: remove sroa from the RUN clause because the optimized input is in use.

[psamolysov]

Colleagues, if the changes look good for you, could you help me with landing? Thank you.

If you have no objections, I would like to use the comments under this review to ask a question about changing the byval promotion scheme with the "usual" one. The following code:

define internal void @f(%struct.ss* byval(%struct.ss) align 4 %b, %struct.ss** align 8 %acc) nounwind  {
entry:
  store %struct.ss* %b, %struct.ss** %acc, align 8
  ret void
}

Currently is optimized to the following one:

define internal void @f(i32 %b.0, i64 %b.1, %struct.ss** align 8 %acc) #0 {
entry:
  %b = alloca %struct.ss, align 4
  %.0 = getelementptr %struct.ss, %struct.ss* %b, i32 0, i32 0
  store i32 %b.0, i32* %.0, align 4
  %.1 = getelementptr %struct.ss, %struct.ss* %b, i32 0, i32 1
  store i64 %b.1, i64* %.1, align 4
 
  store %struct.ss* %b, %struct.ss** %acc, align 8
  ret void
}

So, actually we store not the original pointer of %struct.ss but a pointer to a temporary allocated on the function f's stack frame. Maybe I get byval wrong and %struct.ss* byval(%struct.ss) align 4 %b is also a pointer to a temporary (but an implicitly created) and therefore there is no difference?

[psamolysov]

And I see that the "usual" (non-byval) promotion uses i64 for the second argument of the generated GEP instructions:

  %2 = alloca %struct.A, align 32
  %3 = getelementptr inbounds %struct.A, %struct.A* %2, i32 0, i32 0
  store float %0, float* %3, align 32
  %4 = getelementptr inbounds %struct.A, %struct.A* %2, i32 0, i32 2
  store i64 2, i64* %4, align 16

; the struct is ready, use GEP and load to prepare new values for the arguments
  %5 = getelementptr %struct.A, %struct.A* %2, i64 0, i32 0 ; i64 0, not i32 0
  %.val = load float, float* %5, align 32
  %6 = getelementptr %struct.A, %struct.A* %2, i64 0, i32 2 ; i64 0, not i32 0
  %.val1 = load i64, i64* %6, align 16

Does this work as designed?

[psamolysov]

I've prepared a patch that replaces byval promotion with usual (non-byval) one with allowed stores. The patch is based on this one, so I will be able to open the review after landing this one. If you could help me with landing, it would be great. Thanks a lot in advance.

[nikic]

Sorry for the delay, I have landed the change now. I'd recommend you to request commit access, see https://llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access for instructions.

[psamolysov]

@nikic Thank you for landing and suggestion.

[nikic]

In D124514#3491237, @psamolysov wrote:

And I see that the "usual" (non-byval) promotion uses i64 for the second argument of the generated GEP instructions:
[...]
Does this work as designed?

The index type to use is specified by DataLayout -- however, other index types will be automatically sign extended or truncated. So it's fine either way, though using the correct index type (i64 by default) is preferred. Struct indices always use i32 though.

llvm/lib/Transforms/IPO/ArgumentPromotion.cpp

static bool canPaddingBeAccessed(Argument *Arg) {
 
   // Scan through the uses recursively to make sure the pointer is always used
   // sanely.
   SmallVector<Value *, 16> WorkList(Arg->users());
   while (!WorkList.empty()) {
     Value *V = WorkList.pop_back_val();
     if (isa<GetElementPtrInst>(V) || isa<PHINode>(V)) {
       if (PtrValues.insert(V).second)
-        llvm::append_range(WorkList, V->users());
+        append_range(WorkList, V->users());
     } else if (StoreInst *Store = dyn_cast<StoreInst>(V)) {
       Stores.push_back(Store);
     } else if (!isa<LoadInst>(V)) {
       return true;
     }
   }
 
   // Check to make sure the pointers aren't captured
if (PtrArg->hasStructRetAttr()) {
       F->addParamAttr(ArgNo, Attribute::NoAlias);
       for (Use &U : F->uses()) {
         CallBase &CB = cast<CallBase>(*U.getUser());
         CB.removeParamAttr(ArgNo, Attribute::StructRet);
         CB.addParamAttr(ArgNo, Attribute::NoAlias);
       }
     }
 
-    // If this is a byval argument, and if the aggregate type is small, just
-    // pass the elements, which is always safe, if the passed value is densely
-    // packed or if we can prove the padding bytes are never accessed.
+    // If we can promote the pointer to its value.
+    SmallVector<OffsetAndArgPart, 4> ArgParts;
+    if (findArgParts(PtrArg, DL, AAR, MaxElements, IsRecursive, ArgParts)) {
+      SmallVector<Type *, 4> Types;
+      for (const auto &Pair : ArgParts)
+        Types.push_back(Pair.second.Ty);
+
+      if (areTypesABICompatible(Types, *F, TTI)) {
+        ArgsToPromote.insert({PtrArg, std::move(ArgParts)});
+        continue;
+      }
+    }
+
+    // Otherwise, if this is a byval argument, and if the aggregate type is
+    // small, just pass the elements, which is always safe, if the passed value
+    // is densely packed or if we can prove the padding bytes are never
+    // accessed.
     //
     // Only handle arguments with specified alignment; if it's unspecified, the
     // actual alignment of the argument is target-specific.
     Type *ByValTy = PtrArg->getParamByValType();
     bool IsSafeToPromote =
         ByValTy && PtrArg->getParamAlign() &&
         (ArgumentPromotionPass::isDenselyPacked(ByValTy, DL) ||
          !canPaddingBeAccessed(PtrArg));
-    if (IsSafeToPromote) {
-      if (StructType *STy = dyn_cast<StructType>(ByValTy)) {
-        if (MaxElements > 0 && STy->getNumElements() > MaxElements) {
-          LLVM_DEBUG(dbgs() << "ArgPromotion disables promoting argument '"
-                            << PtrArg->getName()
-                            << "' because it would require adding more"
-                            << " than " << MaxElements
-                            << " arguments to the function.\n");
-          continue;
-        }
-
-        SmallVector<Type *, 4> Types;
-        append_range(Types, STy->elements());
+    if (!IsSafeToPromote) {
+      LLVM_DEBUG(dbgs() << "ArgPromotion disables passing the elements of"
+                        << " the argument '" << PtrArg->getName()
+                        << "' because it is not safe.\n");
+      continue;
+    }
+        LLVM_DEBUG(dbgs() << "ArgPromotion disables passing the elements of"
+                          << " the argument '" << PtrArg->getName()
 
-        // If all the elements are single-value types, we can promote it.
-        bool AllSimple =
-            all_of(Types, [](Type *Ty) { return Ty->isSingleValueType(); });
 
-        // Safe to transform, don't even bother trying to "promote" it.
-        // Passing the elements as a scalar will allow sroa to hack on
-        // the new alloca we introduce.
-        if (AllSimple && areTypesABICompatible(Types, *F, TTI)) {
-          ByValArgsToTransform.insert(PtrArg);
-          continue;
-        }
-      }
-    }
-
-    // Otherwise, see if we can promote the pointer to its value.
-    SmallVector<OffsetAndArgPart, 4> ArgParts;
-    if (findArgParts(PtrArg, DL, AAR, MaxElements, IsRecursive, ArgParts)) {
-      SmallVector<Type *, 4> Types;
-      for (const auto &Pair : ArgParts)
-        Types.push_back(Pair.second.Ty);
-
-      if (areTypesABICompatible(Types, *F, TTI))
-        ArgsToPromote.insert({PtrArg, std::move(ArgParts)});
+      // Safe to transform. Passing the elements as a scalar will allow sroa to
+      // hack on the new alloca we introduce.
+      if (AllSimple && areTypesABICompatible(Types, *F, TTI))
     }
   }
 
   // No promotable pointer arguments.
   if (ArgsToPromote.empty() && ByValArgsToTransform.empty())
     return nullptr;
 
   return doPromotion(F, ArgsToPromote, ByValArgsToTransform, ReplaceCallSite);

llvm/test/Transforms/ArgumentPromotion/byval-through-pointer-promotion.ll

+; RUN: opt -passes=argpromotion -S %s | FileCheck %s
+
+%struct.A = type { float, [12 x i8], i64, [8 x i8] }
+
+define internal float @callee(%struct.A* byval(%struct.A) align 32 %0) {
+; CHECK-LABEL: define {{[^@]+}}@callee
+; CHECK-SAME: (float [[ARG_0:%.*]], i64 [[ARG_1:%.*]]) {
+; CHECK-NEXT:    [[SUM:%.*]] = fadd float 0.000000e+00, [[ARG_0]]
+; CHECK-NEXT:    [[COEFF:%.*]] = uitofp i64 [[ARG_1]] to float
+; CHECK-NEXT:    [[RES:%.*]] = fmul float [[SUM]], [[COEFF]]
+; CHECK-NEXT:    ret float [[RES]]
+;
+  %2 = getelementptr inbounds %struct.A, %struct.A* %0, i32 0, i32 0
+  %3 = load float, float* %2, align 32
+  %4 = fadd float 0.000000e+00, %3
+  %5 = getelementptr inbounds %struct.A, %struct.A* %0, i32 0, i32 2
+  %6 = load i64, i64* %5, align 16
+  %7 = uitofp i64 %6 to float
+  %8 = fmul float %4, %7
+  ret float %8
+}
+
+define float @caller(float %0) {
+; CHECK-LABEL: define {{[^@]+}}@caller
+; CHECK-SAME: (float [[ARG_0:%.*]]) {
+; CHECK-NEXT:    [[TMP_0:%.*]] = alloca %struct.A, align 32
+; CHECK-NEXT:    [[FL_PTR_0:%.*]] = getelementptr inbounds %struct.A, %struct.A* [[TMP_0]], i32 0, i32 0
+; CHECK-NEXT:    store float [[ARG_0]], float* [[FL_PTR_0]], align 32
+; CHECK-NEXT:    [[I64_PTR_0:%.*]] = getelementptr inbounds %struct.A, %struct.A* [[TMP_0]], i32 0, i32 2
+; CHECK-NEXT:    store i64 2, i64* [[I64_PTR_0]], align 16
+; CHECK-NEXT:    [[FL_PTR_1:%.*]] = getelementptr %struct.A, %struct.A* [[TMP_0]], i64 0, i32 0
+; CHECK-NEXT:    [[FL_VAL:%.*]] = load float, float* [[FL_PTR_1]], align 32
+; CHECK-NEXT:    [[I64_PTR_1:%.*]] = getelementptr %struct.A, %struct.A* [[TMP_0]], i64 0, i32 2
+; CHECK-NEXT:    [[I64_VAL:%.*]] = load i64, i64* [[I64_PTR_1]], align 16
+; CHECK-NEXT:    [[RES:%.*]] = call noundef float @callee(float [[FL_VAL]], i64 [[I64_VAL]])
+; CHECK-NEXT:    ret float [[RES]]
+;
+  %2 = alloca %struct.A, align 32
+  %3 = getelementptr inbounds %struct.A, %struct.A* %2, i32 0, i32 0
+  store float %0, float* %3, align 32
+  %4 = getelementptr inbounds %struct.A, %struct.A* %2, i32 0, i32 2
+  store i64 2, i64* %4, align 16
+  %5 = call noundef float @callee(%struct.A* byval(%struct.A) align 32 %2)
+  ret float %5
+}

llvm/test/Transforms/ArgumentPromotion/dbg.ll

 }
 
 %struct.pair = type { i32, i32 }
 
 define internal void @test_byval(%struct.pair* byval(%struct.pair) align 4 %P) {
 ; CHECK-LABEL: define {{[^@]+}}@test_byval
 ; CHECK-SAME: (i32 [[P_0:%.*]], i32 [[P_1:%.*]]) {
 ; CHECK-NEXT:    [[P:%.*]] = alloca [[STRUCT_PAIR:%.*]], align 4
-; CHECK-NEXT:    [[DOT0:%.*]] = getelementptr [[STRUCT_PAIR]], %struct.pair* [[P]], i32 0, i32 0
+; CHECK-NEXT:    [[DOT0:%.*]] = getelementptr [[STRUCT_PAIR]], [[STRUCT_PAIR]]* [[P]], i32 0, i32 0
 ; CHECK-NEXT:    store i32 [[P_0]], i32* [[DOT0]], align 4
-; CHECK-NEXT:    [[DOT1:%.*]] = getelementptr [[STRUCT_PAIR]], %struct.pair* [[P]], i32 0, i32 1
+; CHECK-NEXT:    [[DOT1:%.*]] = getelementptr [[STRUCT_PAIR]], [[STRUCT_PAIR]]* [[P]], i32 0, i32 1
 ; CHECK-NEXT:    store i32 [[P_1]], i32* [[DOT1]], align 4
+; CHECK-NEXT:    [[SINK:%.*]] = alloca i32*, align 8
+; CHECK-NEXT:    [[DOT2:%.*]] = getelementptr [[STRUCT_PAIR]], [[STRUCT_PAIR]]* [[P]], i32 0, i32 0
+; CHECK-NEXT:    store i32* [[DOT2]], i32** [[SINK]], align 8
 ; CHECK-NEXT:    ret void
 ;
+  %1 = alloca i32*, align 8
+  %2 = getelementptr %struct.pair, %struct.pair* %P, i32 0, i32 0
+  store i32* %2, i32** %1, align 8 ; to protect from "usual" promotion
   ret void
 }
 
 define void @caller(i32** %Y, %struct.pair* %P) {
 ; CHECK-LABEL: define {{[^@]+}}@caller
 ; CHECK-SAME: (i32** [[Y:%.*]], %struct.pair* [[P:%.*]]) {
 ; CHECK-NEXT:    [[Y_VAL:%.*]] = load i32*, i32** [[Y]], align 8, !dbg [[DBG4:![0-9]+]]
 ; CHECK-NEXT:    [[Y_VAL_VAL:%.*]] = load i32, i32* [[Y_VAL]], align 8, !dbg [[DBG4]]

llvm/test/Transforms/ArgumentPromotion/fp80.ll

entry:
   %result = load i8, i8* %gep
   ret i8 %result
 }
 
 define internal x86_fp80 @UseLongDoubleSafely(%union.u* byval(%union.u) align 16 %arg) {
 ; CHECK-LABEL: define {{[^@]+}}@UseLongDoubleSafely
 ; CHECK-SAME: (x86_fp80 [[ARG_0:%.*]]) {
 ; CHECK-NEXT:    [[ARG:%.*]] = alloca [[UNION_U:%.*]], align 16
-; CHECK-NEXT:    [[DOT0:%.*]] = getelementptr [[UNION_U]], %union.u* [[ARG]], i32 0, i32 0
+; CHECK-NEXT:    [[DOT0:%.*]] = getelementptr [[UNION_U]], [[UNION_U]]* [[ARG]], i32 0, i32 0
 ; CHECK-NEXT:    store x86_fp80 [[ARG_0]], x86_fp80* [[DOT0]], align 16
-; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds [[UNION_U]], %union.u* [[ARG]], i64 0, i32 0
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds [[UNION_U]], [[UNION_U]]* [[ARG]], i64 0, i32 0
+; CHECK-NEXT:    [[IDX_P:%.*]] = alloca i64, align 8
+; CHECK-NEXT:    store i64 0, i64* [[IDX_P]], align 8
+; CHECK-NEXT:    [[IDX:%.*]] = load i64, i64* [[IDX_P]], align 8
+; CHECK-NEXT:    [[GEP_IDX:%.*]] = getelementptr inbounds [[UNION_U]], [[UNION_U]]* [[ARG]], i64 [[IDX]], i32 0
 ; CHECK-NEXT:    [[FP80:%.*]] = load x86_fp80, x86_fp80* [[GEP]], align 16
 ; CHECK-NEXT:    ret x86_fp80 [[FP80]]
 ;
   %gep = getelementptr inbounds %union.u, %union.u* %arg, i64 0, i32 0
+  %idx_slot = alloca i64, align 8
+  store i64 0, i64* %idx_slot, align 8
+  %idx = load i64, i64* %idx_slot, align 8
+  %gep_idx = getelementptr inbounds %union.u, %union.u* %arg, i64 %idx, i32 0 ; to protect from "usual" promotion
   %fp80 = load x86_fp80, x86_fp80* %gep
   ret x86_fp80 %fp80
 }
 
 define internal i64 @AccessPaddingOfStruct(%struct.Foo* byval(%struct.Foo) %a) {
 ; CHECK-LABEL: define {{[^@]+}}@AccessPaddingOfStruct
 ; CHECK-SAME: (i64 [[A_0_VAL:%.*]]) {
 ; CHECK-NEXT:    ret i64 [[A_0_VAL]]