path: root/lib/Transforms/Utils/PromoteMemoryToRegister.cpp

//===- PromoteMemoryToRegister.cpp - Convert allocas to registers ---------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file promotes memory references to be register references.  It promotes
// alloca instructions which only have loads and stores as uses.  An alloca is
// transformed by using dominator frontiers to place PHI nodes, then traversing
// the function in depth-first order to rewrite loads and stores as appropriate.
// This is just the standard SSA construction algorithm to construct "pruned"
// SSA form.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "mem2reg"
#include "llvm/Transforms/Utils/PromoteMemToReg.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Metadata.h"
#include "llvm/Analysis/DebugInfo.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/AliasSetTracker.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/CFG.h"
#include <algorithm>
using namespace llvm;

STATISTIC(NumLocalPromoted, "Number of alloca's promoted within one block");
STATISTIC(NumSingleStore,   "Number of alloca's promoted with a single store");
STATISTIC(NumDeadAlloca,    "Number of dead alloca's removed");
STATISTIC(NumPHIInsert,     "Number of PHI nodes inserted");

namespace llvm {
template<>
struct DenseMapInfo<std::pair<BasicBlock*, unsigned> > {
  typedef std::pair<BasicBlock*, unsigned> EltTy;
  static inline EltTy getEmptyKey() {
    return EltTy(reinterpret_cast<BasicBlock*>(-1), ~0U);
  }
  static inline EltTy getTombstoneKey() {
    return EltTy(reinterpret_cast<BasicBlock*>(-2), 0U);
  }
  static unsigned getHashValue(const std::pair<BasicBlock*, unsigned> &Val) {
    return DenseMapInfo<void*>::getHashValue(Val.first) + Val.second*2;
  }
  static bool isEqual(const EltTy &LHS, const EltTy &RHS) {
    return LHS == RHS;
  }
};
}

/// isAllocaPromotable - Return true if this alloca is legal for promotion.
/// This is true if there are only loads and stores to the alloca.
///
bool llvm::isAllocaPromotable(const AllocaInst *AI) {
  // FIXME: If the memory unit is of pointer or integer type, we can permit
  // assignments to subsections of the memory unit.

  // Only allow direct and non-volatile loads and stores...
  for (Value::const_use_iterator UI = AI->use_begin(), UE = AI->use_end();
       UI != UE; ++UI) {   // Loop over all of the uses of the alloca
    const User *U = *UI;
    if (const LoadInst *LI = dyn_cast<LoadInst>(U)) {
      if (LI->isVolatile())
        return false;
    } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) {
      if (SI->getOperand(0) == AI)
        return false;   // Don't allow a store OF the AI, only INTO the AI.
      if (SI->isVolatile())
        return false;
    } else {
      return false;
    }
  }

  return true;
}

/// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic describing the
/// alloca 'V', if any.
static DbgDeclareInst *FindAllocaDbgDeclare(Value *V) {
  if (MDNode *DebugNode = MDNode::getIfExists(V->getContext(), &V, 1))
    for (Value::use_iterator UI = DebugNode->use_begin(),
         E = DebugNode->use_end(); UI != E; ++UI)
      if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(*UI))
        return DDI;

  return 0;
}

namespace {
  struct AllocaInfo;

  // Data package used by RenamePass()
  class RenamePassData {
  public:
    typedef std::vector<Value *> ValVector;
    
    RenamePassData() : BB(NULL), Pred(NULL), Values() {}
    RenamePassData(BasicBlock<