<commit_before>//===-- ArgumentPromotion.cpp - Promote by-reference arguments ------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass promotes "by reference" arguments to be "by value" arguments.  In
// practice, this means looking for internal functions that have pointer
// arguments.  If it can prove, through the use of alias analysis, that an
// argument is *only* loaded, then it can pass the value into the function
// instead of the address of the value.  This can cause recursive simplification
// of code and lead to the elimination of allocas (especially in C++ template
// code like the STL).
//
// This pass also handles aggregate arguments that are passed into a function,
// scalarizing them if the elements of the aggregate are only loaded.  Note that
// by default it refuses to scalarize aggregates which would require passing in
// more than three operands to the function, because passing thousands of
// operands for a large array or structure is unprofitable! This limit can be
// configured or disabled, however.
//
// Note that this transformation could also be done for arguments that are only
// stored to (returning the value instead), but does not currently.  This case
// would be best handled when and if LLVM begins supporting multiple return
// values from functions.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "argpromotion"
#include "llvm/Transforms/IPO.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Module.h"
#include "llvm/CallGraphSCCPass.h"
#include "llvm/Instructions.h"
#include "llvm/LLVMContext.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include <set>
using namespace llvm;

STATISTIC(NumArgumentsPromoted , "Number of pointer arguments promoted");
STATISTIC(NumAggregatesPromoted, "Number of aggregate arguments promoted");
STATISTIC(NumByValArgsPromoted , "Number of byval arguments promoted");
STATISTIC(NumArgumentsDead     , "Number of dead pointer args eliminated");

namespace {
  /// ArgPromotion - The 'by reference' to 'by value' argument promotion pass.
  ///
  struct ArgPromotion : public CallGraphSCCPass {
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.addRequired<AliasAnalysis>();
      CallGraphSCCPass::getAnalysisUsage(AU);
    }

    virtual bool runOnSCC(std::vector<CallGraphNode *> &SCC);
    static char ID; // Pass identification, replacement for typeid
    explicit ArgPromotion(unsigned maxElements = 3)
      : CallGraphSCCPass(&ID), maxElements(maxElements) {}

    /// A vector used to hold the indices of a single GEP instruction
    typedef std::vector<uint64_t> IndicesVector;

  private:
    CallGraphNode *PromoteArguments(CallGraphNode *CGN);
    bool isSafeToPromoteArgument(Argument *Arg, bool isByVal) const;
    CallGraphNode *DoPromotion(Function *F,
                               SmallPtrSet<Argument*, 8> &ArgsToPromote,
                               SmallPtrSet<Argument*, 8> &ByValArgsToTransform);
    /// The maximum number of elements to expand, or 0 for unlimited.
    unsigned maxElements;
  };
}

char ArgPromotion::ID = 0;
static RegisterPass<ArgPromotion>
X("argpromotion", "Promote 'by reference' arguments to scalars");

Pass *llvm::createArgumentPromotionPass(unsigned maxElements) {
  return new ArgPromotion(maxElements);
}

bool ArgPromotion::runOnSCC(std::vector<CallGraphNode *> &SCC) {
  bool Changed = false, LocalChange;

  do {  // Iterate until we stop promoting from this SCC.
    LocalChange = false;
    // Attempt to promote arguments from all functions in this SCC.
    for (unsigned i = 0, e = SCC.size(); i != e; ++i)
      if (CallGraphNode *CGN = PromoteArguments(SCC[i])) {
        LocalChange = true;
        SCC[i] = CGN;
      }
    Changed |= LocalChange;               // Remember that we changed something.
  } while (LocalChange);

  return Changed;
}

/// PromoteArguments - This method checks the specified function to see if there
/// are any promotable arguments and if it is safe to promote the function (for
/// example, all callers are direct).  If safe to promote some arguments, it
/// calls the DoPromotion method.
///
CallGraphNode *ArgPromotion::PromoteArguments(CallGraphNode *CGN) {
  Function *F = CGN->getFunction();

  // Make sure that it is local to this module.
  if (!F || !F->hasLocalLinkage()) return 0;

  // First check: see if there are any pointer arguments!  If not, quick exit.
  SmallVector<std::pair<Argument*, unsigned>, 16> PointerArgs;
  unsigned ArgNo = 0;
  for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
       I != E; ++I, ++ArgNo)
    if (I->getType()->isPointerTy())
      PointerArgs.push_back(std::pair<Argument*, unsigned>(I, ArgNo));
  if (PointerArgs.empty()) return 0;

  // Second check: make sure that all callers are direct callers.  We can't
  // transform functions that have indirect callers.
  if (F->hasAddressTaken())
    return 0;

  // 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 (unsigned i = 0; i != PointerArgs.size(); ++i) {
    bool isByVal = F->paramHasAttr(PointerArgs[i].second+1, Attribute::ByVal);

    // If this is a byval argument, and if the aggregate type is small, just
    // pass the elements, which is always safe.
    Argument *PtrArg = PointerArgs[i].first;
    if (isByVal) {
      const Type *AgTy = cast<PointerType>(PtrArg->getType())->getElementType();
      if (const 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");
        } else {
          // If all the elements are single-value types, we can promote it.
          bool AllSimple = true;
          for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
            if (!STy->getElementType(i)->isSingleValueType()) {
              AllSimple = false;
              break;
            }

          // Safe to transform, don't even bother trying to "promote" it.
          // Passing the elements as a scalar will allow scalarrepl to hack on
          // the new alloca we introduce.
          if (AllSimple) {
            ByValArgsToTransform.insert(PtrArg);
            continue;
          }
        }
      }
    }

    // Otherwise, see if we can promote the pointer to its value.
    if (isSafeToPromoteArgument(PtrArg, isByVal))
      ArgsToPromote.insert(PtrArg);
  }

  // No promotable pointer arguments.
  if (ArgsToPromote.empty() && ByValArgsToTransform.empty()) 
    return 0;

  return DoPromotion(F, ArgsToPromote, ByValArgsToTransform);
}

/// IsAlwaysValidPointer - Return true if the specified pointer is always legal
/// to load.
static bool IsAlwaysValidPointer(Value *V) {
  if (isa<AllocaInst>(V) || isa<GlobalVariable>(V)) return true;
  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V))
    return IsAlwaysValidPointer(GEP->getOperand(0));
  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
    if (CE->getOpcode() == Instruction::GetElementPtr)
      return IsAlwaysValidPointer(CE->getOperand(0));

  return false;
}

/// AllCalleesPassInValidPointerForArgument - Return true if we can prove that
/// all callees pass in a valid pointer for the specified function argument.
static bool AllCalleesPassInValidPointerForArgument(Argument *Arg) {
  Function *Callee = Arg->getParent();

  unsigned ArgNo = std::distance(Callee->arg_begin(),
                                 Function::arg_iterator(Arg));

  // Look at all call sites of the function.  At this pointer we know we only
  // have direct callees.
  for (Value::use_iterator UI = Callee->use_begin(), E = Callee->use_end();
       UI != E; ++UI) {
    CallSite CS = CallSite::get(*UI);
    assert(CS.getInstruction() && "Should only have direct calls!");

    if (!IsAlwaysValidPointer(CS.getArgument(ArgNo)))
      return false;
  }
  return true;
}

/// Returns true if Prefix is a prefix of longer. That means, Longer has a size
/// that is greater than or equal to the size of prefix, and each of the
/// elements in Prefix is the same as the corresponding elements in Longer.
///
/// This means it also returns true when Prefix and Longer are equal!
static bool IsPrefix(const ArgPromotion::IndicesVector &Prefix,
                     const ArgPromotion::IndicesVector &Longer) {
  if (Prefix.size() > Longer.size())
    return false;
  for (unsigned i = 0, e = Prefix.size(); i != e; ++i)
    if (Prefix[i] != Longer[i])
      return false;
  return true;
}


/// Checks if Indices, or a prefix of Indices, is in Set.
static bool PrefixIn(const ArgPromotion::IndicesVector &Indices,
                     std::set<ArgPromotion::IndicesVector> &Set) {
    std::set<ArgPromotion::IndicesVector>::iterator Low;
    Low = Set.upper_bound(Indices);
    if (Low != Set.begin())
      Low--;
    // Low is now the last element smaller than or equal to Indices. This means
    // it points to a prefix of Indices (possibly Indices itself), if such
    // prefix exists.
    //
    // This load is safe if any prefix of its operands is safe to load.
    return Low != Set.end() && IsPrefix(*Low, Indices);
}

/// Mark the given indices (ToMark) as safe in the given set of indices
/// (Safe). Marking safe usually means adding ToMark to Safe. However, if there
/// is already a prefix of Indices in Safe, Indices are implicitely marked safe
/// already. Furthermore, any indices that Indices is itself a prefix of, are
/// removed from Safe (since they are implicitely safe because of Indices now).
static void MarkIndicesSafe(const ArgPromotion::IndicesVector &ToMark,
                            std::set<ArgPromotion::IndicesVector> &Safe) {
  std::set<ArgPromotion::IndicesVector>::iterator Low;
  Low = Safe.upper_bound(ToMark);
  // Guard against the case where Safe is empty
  if (Low != Safe.begin())
    Low--;
  // Low is now the last element smaller than or equal to Indices. This
  // means it points to a prefix of Indices (possibly Indices itself), if
  // such prefix exists.
  if (Low != Safe.end()) {
    if (IsPrefix(*Low, ToMark))
      // If there is already a prefix of these indices (or exactly these
      // indices) marked a safe, don't bother adding these indices
      return;

    // Increment Low, so we can use it as a "insert before" hint
    ++Low;
  }
  // Insert
  Low = Safe.insert(Low, ToMark);
  ++Low;
  // If there we're a prefix of longer index list(s), remove those
  std::set<ArgPromotion::IndicesVector>::iterator End = Safe.end();
  while (Low != End && IsPrefix(ToMark, *Low)) {
    std::set<ArgPromotion::IndicesVector>::iterator Remove = Low;
    ++Low;
    Safe.erase(Remove);
  }
}

/// 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 {
  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.
  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 || AllCalleesPassInValidPointerForArgument(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();
       I != E; ++I)
    if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
      Value *V = LI->getPointerOperand();
      if (GetElementPtrInst *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)
            if (ConstantInt *CI = dyn_cast<ConstantInt>(*II))
              Indices.push_back(CI->getSExtValue());<commit_msg>Correct whitespace.<commit_after>//===-- ArgumentPromotion.cpp - Promote by-reference arguments ------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass promotes "by reference" arguments to be "by value" arguments.  In
// practice, this means looking for internal functions that have pointer
// arguments.  If it can prove, through the use of alias analysis, that an
// argument is *only* loaded, then it can pass the value into the function
// instead of the address of the value.  This can cause recursive simplification
// of code and lead to the elimination of allocas (especially in C++ template
// code like the STL).
//
// This pass also handles aggregate arguments that are passed into a function,
// scalarizing them if the elements of the aggregate are only loaded.  Note that
// by default it refuses to scalarize aggregates which would require passing in
// more than three operands to the function, because passing thousands of
// operands for a large array or structure is unprofitable! This limit can be
// configured or disabled, however.
//
// Note that this transformation could also be done for arguments that are only
// stored to (returning the value instead), but does not currently.  This case
// would be best handled when and if LLVM begins supporting multiple return
// values from functions.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "argpromotion"
#include "llvm/Transforms/IPO.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Module.h"
#include "llvm/CallGraphSCCPass.h"
#include "llvm/Instructions.h"
#include "llvm/LLVMContext.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include <set>
using namespace llvm;

STATISTIC(NumArgumentsPromoted , "Number of pointer arguments promoted");
STATISTIC(NumAggregatesPromoted, "Number of aggregate arguments promoted");
STATISTIC(NumByValArgsPromoted , "Number of byval arguments promoted");
STATISTIC(NumArgumentsDead     , "Number of dead pointer args eliminated");

namespace {
  /// ArgPromotion - The 'by reference' to 'by value' argument promotion pass.
  ///
  struct ArgPromotion : public CallGraphSCCPass {
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.addRequired<AliasAnalysis>();
      CallGraphSCCPass::getAnalysisUsage(AU);
    }

    virtual bool runOnSCC(std::vector<CallGraphNode *> &SCC);
    static char ID; // Pass identification, replacement for typeid
    explicit ArgPromotion(unsigned maxElements = 3)
      : CallGraphSCCPass(&ID), maxElements(maxElements) {}

    /// A vector used to hold the indices of a single GEP instruction
    typedef std::vector<uint64_t> IndicesVector;

  private:
    CallGraphNode *PromoteArguments(CallGraphNode *CGN);
    bool isSafeToPromoteArgument(Argument *Arg, bool isByVal) const;
    CallGraphNode *DoPromotion(Function *F,
                               SmallPtrSet<Argument*, 8> &ArgsToPromote,
                               SmallPtrSet<Argument*, 8> &ByValArgsToTransform);
    /// The maximum number of elements to expand, or 0 for unlimited.
    unsigned maxElements;
  };
}

char ArgPromotion::ID = 0;
static RegisterPass<ArgPromotion>
X("argpromotion", "Promote 'by reference' arguments to scalars");

Pass *llvm::createArgumentPromotionPass(unsigned maxElements) {
  return new ArgPromotion(maxElements);
}

bool ArgPromotion::runOnSCC(std::vector<CallGraphNode *> &SCC) {
  bool Changed = false, LocalChange;

  do {  // Iterate until we stop promoting from this SCC.
    LocalChange = false;
    // Attempt to promote arguments from all functions in this SCC.
    for (unsigned i = 0, e = SCC.size(); i != e; ++i)
      if (CallGraphNode *CGN = PromoteArguments(SCC[i])) {
        LocalChange = true;
        SCC[i] = CGN;
      }
    Changed |= LocalChange;               // Remember that we changed something.
  } while (LocalChange);

  return Changed;
}

/// PromoteArguments - This method checks the specified function to see if there
/// are any promotable arguments and if it is safe to promote the function (for
/// example, all callers are direct).  If safe to promote some arguments, it
/// calls the DoPromotion method.
///
CallGraphNode *ArgPromotion::PromoteArguments(CallGraphNode *CGN) {
  Function *F = CGN->getFunction();

  // Make sure that it is local to this module.
  if (!F || !F->hasLocalLinkage()) return 0;

  // First check: see if there are any pointer arguments!  If not, quick exit.
  SmallVector<std::pair<Argument*, unsigned>, 16> PointerArgs;
  unsigned ArgNo = 0;
  for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
       I != E; ++I, ++ArgNo)
    if (I->getType()->isPointerTy())
      PointerArgs.push_back(std::pair<Argument*, unsigned>(I, ArgNo));
  if (PointerArgs.empty()) return 0;

  // Second check: make sure that all callers are direct callers.  We can't
  // transform functions that have indirect callers.
  if (F->hasAddressTaken())
    return 0;

  // 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 (unsigned i = 0; i != PointerArgs.size(); ++i) {
    bool isByVal = F->paramHasAttr(PointerArgs[i].second+1, Attribute::ByVal);

    // If this is a byval argument, and if the aggregate type is small, just
    // pass the elements, which is always safe.
    Argument *PtrArg = PointerArgs[i].first;
    if (isByVal) {
      const Type *AgTy = cast<PointerType>(PtrArg->getType())->getElementType();
      if (const 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");
        } else {
          // If all the elements are single-value types, we can promote it.
          bool AllSimple = true;
          for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
            if (!STy->getElementType(i)->isSingleValueType()) {
              AllSimple = false;
              break;
            }

          // Safe to transform, don't even bother trying to "promote" it.
          // Passing the elements as a scalar will allow scalarrepl to hack on
          // the new alloca we introduce.
          if (AllSimple) {
            ByValArgsToTransform.insert(PtrArg);
            continue;
          }
        }
      }
    }

    // Otherwise, see if we can promote the pointer to its value.
    if (isSafeToPromoteArgument(PtrArg, isByVal))
      ArgsToPromote.insert(PtrArg);
  }

  // No promotable pointer arguments.
  if (ArgsToPromote.empty() && ByValArgsToTransform.empty()) 
    return 0;

  return DoPromotion(F, ArgsToPromote, ByValArgsToTransform);
}

/// IsAlwaysValidPointer - Return true if the specified pointer is always legal
/// to load.
static bool IsAlwaysValidPointer(Value *V) {
  if (isa<AllocaInst>(V) || isa<GlobalVariable>(V)) return true;
  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V))
    return IsAlwaysValidPointer(GEP->getOperand(0));
  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
    if (CE->getOpcode() == Instruction::GetElementPtr)
      return IsAlwaysValidPointer(CE->getOperand(0));

  return false;
}

/// AllCalleesPassInValidPointerForArgument - Return true if we can prove that
/// all callees pass in a valid pointer for the specified function argument.
static bool AllCalleesPassInValidPointerForArgument(Argument *Arg) {
  Function *Callee = Arg->getParent();

  unsigned ArgNo = std::distance(Callee->arg_begin(),
                                 Function::arg_iterator(Arg));

  // Look at all call sites of the function.  At this pointer we know we only
  // have direct callees.
  for (Value::use_iterator UI = Callee->use_begin(), E = Callee->use_end();
       UI != E; ++UI) {
    CallSite CS = CallSite::get(*UI);
    assert(CS.getInstruction() && "Should only have direct calls!");

    if (!IsAlwaysValidPointer(CS.getArgument(ArgNo)))
      return false;
  }
  return true;
}

/// Returns true if Prefix is a prefix of longer. That means, Longer has a size
/// that is greater than or equal to the size of prefix, and each of the
/// elements in Prefix is the same as the corresponding elements in Longer.
///
/// This means it also returns true when Prefix and Longer are equal!
static bool IsPrefix(const ArgPromotion::IndicesVector &Prefix,
                     const ArgPromotion::IndicesVector &Longer) {
  if (Prefix.size() > Longer.size())
    return false;
  for (unsigned i = 0, e = Prefix.size(); i != e; ++i)
    if (Prefix[i] != Longer[i])
      return false;
  return true;
}


/// Checks if Indices, or a prefix of Indices, is in Set.
static bool PrefixIn(const ArgPromotion::IndicesVector &Indices,
                     std::set<ArgPromotion::IndicesVector> &Set) {
    std::set<ArgPromotion::IndicesVector>::iterator Low;
    Low = Set.upper_bound(Indices);
    if (Low != Set.begin())
      Low--;
    // Low is now the last element smaller than or equal to Indices. This means
    // it points to a prefix of Indices (possibly Indices itself), if such
    // prefix exists.
    //
    // This load is safe if any prefix of its operands is safe to load.
    return Low != Set.end() && IsPrefix(*Low, Indices);
}

/// Mark the given indices (ToMark) as safe in the given set of indices
/// (Safe). Marking safe usually means adding ToMark to Safe. However, if there
/// is already a prefix of Indices in Safe, Indices are implicitely marked safe
/// already. Furthermore, any indices that Indices is itself a prefix of, are
/// removed from Safe (since they are implicitely safe because of Indices now).
static void MarkIndicesSafe(const ArgPromotion::IndicesVector &ToMark,
                            std::set<ArgPromotion::IndicesVector> &Safe) {
  std::set<ArgPromotion::IndicesVector>::iterator Low;
  Low = Safe.upper_bound(ToMark);
  // Guard against the case where Safe is empty
  if (Low != Safe.begin())
    Low--;
  // Low is now the last element smaller than or equal to Indices. This
  // means it points to a prefix of Indices (possibly Indices itself), if
  // such prefix exists.
  if (Low != Safe.end()) {
    if (IsPrefix(*Low, ToMark))
      // If there is already a prefix of these indices (or exactly these
      // indices) marked a safe, don't bother adding these indices
      return;

    // Increment Low, so we can use it as a "insert before" hint
    ++Low;
  }
  // Insert
  Low = Safe.insert(Low, ToMark);
  ++Low;
  // If there we're a prefix of longer index list(s), remove those
  std::set<ArgPromotion::IndicesVector>::iterator End = Safe.end();
  while (Low != End && IsPrefix(ToMark, *Low)) {
    std::set<ArgPromotion::IndicesVector>::iterator Remove = Low;
    ++Low;
    Safe.erase(Remove);
  }
}

/// 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 {
  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.
  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 || AllCalleesPassInValidPointerForArgument(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();
       I != E; ++I)
    if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
      Value *V = LI->getPointerOperand();
      if (GetElementPtrInst *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)
            if (ConstantInt *CI = dyn_cast<ConstantInt>(*II))
              Indices.push_back(CI->getSExtValue());
{'fraction_non_alphanumeric': 0.11730236148636794, 'fraction_numerical': 0.0018948033264325065, 'mean_word_length': 3.07842014882656, 'pattern_counts': {'":': 0, '<': 85, '<?xml version=': 0, '>': 133, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7646462', 'n_tokens_mistral': 8078, 'n_tokens_neox': 7978, 'n_words': 3045}