Create as few pieces of an argument as possible when promoting an argument.

[trentxintong]

Summary

Create as few pieces of an argument as possible when promoting an argument.
When LLVM finds a by-ref argument is only read by the callee and its the safe to dereference.
It could choose to promote this argument to one or more value arguments. Currently it goes through
all the loads and create them at every callsites.

This patch minimize the # of arguments passed in. i.e. If we have an argument thats completely
part of another argument (due to gep in the callee), we do not need to pass in this argument,
instead we do extractvalue from the other argument.

[trentxintong]

Rework how ArgIndices is iterated a bit.

[rnk]

Doesn't SROA remove FCA loads? If so, it seems unlikely that arg promotion will ever see an FCA load.

[trentxintong]

SROA is ran after argument promotion, there is some unpacking in Instcombine as well, but its ran after argument promotion as well.

[trentxintong]

we do advise frontends against generating aggregate loads, but they may do so regardless.

[rnk]

I'm sure there's some obscure reason for this phase ordering. Do we run instcombine before argument promotion? We should turn these FCA loads into GEPs, loads, and insertelements. FCA loads are currently non-canonical, although it is reasonable for a frontend to generate them.

[trentxintong]

Actually we do run one iteration of instcombine before argument promotion. Given that, I feel this is still useful as there are limits on what sort of aggregates we break up, e.g. if the struct has padding, we do not break it up. argprom however may still promote the argument.

lib/Transforms/IPO/ArgumentPromotion.cpp

 ///
 /// This means it also returns true when Prefix and Longer are equal!
 static bool IsPrefix(const IndicesVector &Prefix, const IndicesVector &Longer) {
   if (Prefix.size() > Longer.size())
     return false;
   return std::equal(Prefix.begin(), Prefix.end(), Longer.begin());
 }
 
+/// Return true if the i is a large index that can not be used by extractvalue.
+/// ExtractValue can not accept indices greater than UINT_MAX.
+static bool IsLargeIndex(uint64_t i) { return i > UINT_MAX; }
+
+/// Return the remaining of subtracting APrefix from BPrefix.
+/// This function expects that APrefix is a Prefix of BPrefix.
+static IndicesVector SubtractPrefix(const IndicesVector &APrefix,
+                                    const IndicesVector &BPrefix) {
+  assert(APrefix.size() <= BPrefix.size() &&
+         "Subtracting longer prefix from shorter prefix");
+  return IndicesVector(BPrefix.begin() + APrefix.size(), BPrefix.end());
+}
+
+/// Return true if suffix resulted from APrefix - BPrefix are all small indices.
+static bool HasSmallSuffix(const IndicesVector &APrefix,
+                           const IndicesVector &BPrefix) {
+  auto S = SubtractPrefix(APrefix, BPrefix);
+  return std::find_if(S.begin(), S.end(), IsLargeIndex) == S.end();
+}
+
+/// Return true if suffix resulted from APrefix - BPrefix are all small indices.
+/// And also copy the subtraction results in Suffix.
+static bool GetSmallSuffix(const IndicesVector &APrefix,
+                           const IndicesVector &BPrefix,
+                           std::vector<unsigned> &Suffix) {
+  auto S = SubtractPrefix(APrefix, BPrefix);
+  for (auto i : S) {
+    if (IsLargeIndex(i)) {
+      Suffix.clear();
+      return false;
+    }
+    Suffix.push_back(i);
+  }
+  return true;
+}
 
 /// Checks if Indices, or a prefix of Indices, is in Set.
 static bool PrefixIn(const IndicesVector &Indices,
                      std::set<IndicesVector> &Set) {
     std::set<IndicesVector>::iterator Low;
     Low = Set.upper_bound(Indices);
     if (Low != Set.begin())
       Low--;
if (ByValArgsToTransform.count(&*I)) {
         if (LoadInst *L = dyn_cast<LoadInst>(UI))
           OrigLoad = L;
         else
           // Take any load, we will use it only to update Alias Analysis
           OrigLoad = cast<LoadInst>(UI->user_back());
         OriginalLoads[std::make_pair(&*I, Indices)] = OrigLoad;
       }
 
+      // Create as few promoted arguments as possible. We can value extract a
+      // promoted argument if it is part of another promoted argument.
+      for (ScalarizeTable::iterator MI = ArgIndices.begin(),
+                                    ME = ArgIndices.end();
+           MI != ME; ++MI) {
+        // Make sure we get the proper prefix in case this is a direct load.
+        IndicesVector P = MI->second.empty() ? IndicesVector(0) : MI->second;
+        ScalarizeTable::iterator NI = ArgIndices.begin();
+        while (NI != ArgIndices.end()) {
+          // Erase NI if MI is a prefix of it and we can create an extracted
+          // value from promoted MI.
+          if (MI != NI && IsPrefix(P, NI->second) &&
+              HasSmallSuffix(P, NI->second)) {
+            OriginalLoads.erase(std::make_pair(&*I, NI->second));
+            NI = ArgIndices.erase(NI);
+            continue;
+          }
+          ++NI;
+        }
+      }
+
       // Add a parameter to the function for each element passed in.
       for (const auto &ArgIndex : ArgIndices) {
         // not allowed to dereference ->begin() if size() is 0
         Params.push_back(GetElementPtrInst::getIndexedType(
             cast<PointerType>(I->getType()->getScalarType())->getElementType(),
             ArgIndex.second));
         assert(Params.back());
       }
while (!I->use_empty()) {
                "Load element should sort to front!");
         I2->setName(I->getName()+".val");
         LI->replaceAllUsesWith(&*I2);
         LI->eraseFromParent();
         DEBUG(dbgs() << "*** Promoted load of argument '" << I->getName()
               << "' in function '" << F->getName() << "'\n");
       } else {
         GetElementPtrInst *GEP = cast<GetElementPtrInst>(I->user_back());
+        std::vector<unsigned> Suffix;
         IndicesVector Operands;
         Operands.reserve(GEP->getNumIndices());
         for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end();
              II != IE; ++II)
           Operands.push_back(cast<ConstantInt>(*II)->getSExtValue());
 
         // GEPs with a single 0 index can be merged with direct loads
         if (Operands.size() == 1 && Operands.front() == 0)
           Operands.clear();
 
         Function::arg_iterator TheArg = I2;
         for (ScalarizeTable::iterator It = ArgIndices.begin();
              It->second != Operands; ++It, ++TheArg) {
+          IndicesVector P = It->second.empty() ? IndicesVector(0) : It->second;
+          // Found Operands' prefix.
+          if (IsPrefix(P, Operands) && GetSmallSuffix(P, Operands, Suffix))
+            break;
           assert(It != ArgIndices.end() && "GEP not handled??");
         }
 
         std::string NewName = I->getName();
         for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
             NewName += "." + utostr(Operands[i]);
         }
         NewName += ".val";
         TheArg->setName(NewName);
 
         DEBUG(dbgs() << "*** Promoted agg argument '" << TheArg->getName()
               << "' of function '" << NF->getName() << "'\n");
 
         // All of the uses must be load instructions.  Replace them all with
         // the argument specified by ArgNo.
         while (!GEP->use_empty()) {
+          Value *V = &*TheArg;
+          if (!Suffix.empty())
+            V = ExtractValueInst::Create(V, Suffix, "", &*NF->begin()->begin());
           LoadInst *L = cast<LoadInst>(GEP->user_back());
-          L->replaceAllUsesWith(&*TheArg);
+          L->replaceAllUsesWith(V);
           L->eraseFromParent();
         }
         GEP->eraseFromParent();
       }
     }
 
     // Increment I2 past all of the arguments added for this promoted pointer.
     std::advance(I2, ArgIndices.size());

test/Transforms/ArgumentPromotion/aggregate-promote-overlapping.ll

+; RUN: opt < %s -argpromotion -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.S = type { %struct.P, i32 }
+%struct.P = type { i32, i32 }
+%struct.X = type { i32, i32 }
+
+declare void @take_p(%struct.P) readnone
+declare void @take_x(%struct.X) readnone
+
+; CHECK-LABEL define internal i32 @promotei_struct(%struct.P
+; CHECK: extractvalue
+define internal i32 @promote_struct(%struct.S*) {
+  %2 = getelementptr inbounds %struct.S, %struct.S* %0, i32 0, i32 0
+  %3 = load %struct.P, %struct.P* %2, align 4
+  call void @take_p(%struct.P %3)
+  %4 = getelementptr inbounds %struct.S, %struct.S* %0, i32 0, i32 0, i32 0
+  %5 = load i32, i32* %4, align 4
+  ret i32 %5
+}
+
+define i32 @caller_struct(%struct.S*) {
+  %2 = call i32 @promote_struct(%struct.S* %0)
+  ret i32 %2
+}
+
+; CHECK-LABEL define internal i32 @promote_array(%struct.X
+; CHECK: extractvalue
+define internal i32 @promote_array([1024 x %struct.X]*) #1 {
+  %2 = getelementptr inbounds [1024 x %struct.X], [1024 x %struct.X]* %0, i64 0, i64 1023
+  %3 = load %struct.X, %struct.X* %2, align 4
+  call void @take_x(%struct.X %3)
+  %4 = getelementptr inbounds [1024 x %struct.X], [1024 x %struct.X]* %0, i64 0, i64 1023, i32 0
+  %5 = load i32, i32* %4, align 4
+  ret i32 %5
+}
+
+define i32 @caller_array([1024 x %struct.X]*) #0 {
+  %2 = call i32 @promote_array([1024 x %struct.X]* %0)
+  ret i32 %2
+}