[MustExec][ArgPromote][WIP] Properly determine which loads are executed

[jdoerfert]

Summary

NOTE: This shows how the MustBeExecutedContextExplorer is used.

ArgumentPromotion, for now, does a custom "is dereferenceable" check.

As tracked in PR42039, this check is broken. This patch uses the
MustBeExecutedContextExplorer to visit all instructions that are
executed when the function is entered, fixing the problem and improving
the result at the same time.

[jdoerfert]

Part of D65186 now.

llvm/lib/Transforms/IPO/ArgumentPromotion.cpp

 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/MemoryLocation.h"
+#include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constants.h"
static void markIndicesSafe(const 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.
-static bool isSafeToPromoteArgument(Argument *Arg, Type *ByValTy, AAResults &AAR,
-                                    unsigned MaxElements) {
+static bool isSafeToPromoteArgument(Argument *Arg, Type *ByValTy,
+                                    AAResults &AAR, unsigned MaxElements,
+                                    MustBeExecutedContextExplorer &Explorer) {
   using GEPIndicesSet = std::set<IndicesVector>;
 
   // 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.
auto UpdateBaseTy = [&](Type *NewBaseTy) {
     if (allCallersPassValidPointerForArgument(Arg, BaseTy)) {
       assert(SafeToUnconditionallyLoad.empty());
       SafeToUnconditionallyLoad.insert(IndicesVector(1, 0));
     }
 
     return true;
   };
 
-  // First, iterate the entry block and mark loads of (geps of) arguments as
-  // safe.
-  BasicBlock &EntryBlock = Arg->getParent()->front();
+
   // Declare this here so we can reuse it
   IndicesVector Indices;
-  for (Instruction &I : EntryBlock)
-    if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
-      Value *V = LI->getPointerOperand();
-      if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V)) {
+  // First, iterate over all instructions executed whenever the function is
+  // reached and mark loads of (geps of) arguments as safe.
+  BasicBlock &EntryBlock = Arg->getParent()->front();
+  for (const Instruction *I : Explorer.range(&EntryBlock.front()))
+    if (auto *LI = dyn_cast<LoadInst>(I)) {
+      const Value *V = LI->getPointerOperand();
+      if (auto *GEP = dyn_cast<GetElementPtrInst>(V)) {
         V = GEP->getPointerOperand();
         if (V == Arg) {
           // This load actually loads (part of) Arg? Check the indices then.
           Indices.reserve(GEP->getNumIndices());
-          for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end();
-               II != IE; ++II)
+          for (auto II = GEP->idx_begin(), IE = GEP->idx_end(); II != IE; ++II)
             if (ConstantInt *CI = dyn_cast<ConstantInt>(*II))
               Indices.push_back(CI->getSExtValue());
             else
               // We found a non-constant GEP index for this argument? Bail out
               // right away, can't promote this argument at all.
               return false;
 
           if (!UpdateBaseTy(GEP->getSourceElementType()))
for (Use &U : Arg->uses()) {
     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(UR)) {
       if (GEP->use_empty()) {
         // Dead GEP's cause trouble later.  Just remove them if we run into
         // them.
         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, ByValTy, AAR, MaxElements);
+        return isSafeToPromoteArgument(Arg, ByValTy, AAR, MaxElements,
+                                       Explorer);
       }
 
       if (!UpdateBaseTy(GEP->getSourceElementType()))
         return false;
 
       // Ensure that all of the indices are constants.
       for (User::op_iterator i = GEP->idx_begin(), e = GEP->idx_end(); i != e;
            ++i)
promoteArguments(Function *F, function_ref<AAResults &(Function &F)> AARGetter,
   for (BasicBlock &BB : *F)
     if (BB.getTerminatingMustTailCall())
       return nullptr;
 
   const DataLayout &DL = F->getParent()->getDataLayout();
 
   AAResults &AAR = AARGetter(*F);
 
+  // TODO: This should be removed once we deduce "dereferenceable" properly.
+  MustBeExecutedContextExplorer Explorer(/* ExploreInterBlock */ true,
+                                         /* ExploreCFGForward */ true,
+                                         /* ExploreCFGBackward */ false,
+                                         /* ExploreFlowSensitive */ true);
+
   // Check to see which arguments are promotable.  If an argument is promotable,
   // add it to ArgsToPromote.
   SmallPtrSet<Argument *, 8> ArgsToPromote;
   SmallPtrSet<Argument *, 8> ByValArgsToTransform;
   for (Argument *PtrArg : PointerArgs) {
     Type *AgTy = cast<PointerType>(PtrArg->getType())->getElementType();
 
     // Replace sret attribute with noalias. This reduces register pressure by
if (isSelfRecursive) {
         if (RecursiveType)
           continue;
       }
     }
 
     // Otherwise, see if we can promote the pointer to its value.
     Type *ByValTy =
         PtrArg->hasByValAttr() ? PtrArg->getParamByValType() : nullptr;
-    if (isSafeToPromoteArgument(PtrArg, ByValTy, AAR, MaxElements))
+    if (isSafeToPromoteArgument(PtrArg, ByValTy, AAR, MaxElements, Explorer))
       ArgsToPromote.insert(PtrArg);
   }
 
   // No promotable pointer arguments.
   if (ArgsToPromote.empty() && ByValArgsToTransform.empty())
     return nullptr;
 
   if (!areFunctionArgsABICompatible(*F, TTI, ArgsToPromote,