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/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::use_const_iterator UI = AI->use_begin(), UE = AI->use_end();
       UI != UE; ++UI)     // Loop over all of the uses of the alloca
    if (const LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
      if (LI->isVolatile())
        return false;
    } else if (const StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
      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;
}

namespace {
  struct AllocaInfo;

  // Data package used by RenamePass()
  class RenamePassData {
  public:
    typedef std::vector<Value *> ValVector;
    
    RenamePassData() : BB(NULL), Pred(NULL), Values() {}
    RenamePassData(BasicBlock *B, BasicBlock *P,
                   const ValVector &V) : BB(B), Pred(P), Values(V) {}
    BasicBlock *BB;
    BasicBlock *Pred;
    ValVector Values;
    
    void swap(RenamePassData &RHS) {
      std::swap(BB, RHS.BB);
      std::swap(Pred, RHS.Pred);
      Values.swap(RHS.Values);
    }
  };
  
  /// LargeBlockInfo - This assigns and keeps a per-bb relative ordering of
  /// load/store instructions in the block that directly load or store an alloca.
  ///
  /// This functionality is important because it avoids scanning large basic
  /// blocks multiple times when promoting many allocas in the same block.
  class LargeBlockInfo {
    /// InstNumbers - For each instruction that we track, keep the index of the
    /// instruction.  The index starts out as the number of the instruction from
    /// the start of the block.
    DenseMap<const Instruction *, unsigned> InstNumbers;
  public:
    
    /// isInterestingInstruction - This code only looks at accesses to allocas.
    static bool isInterestingInstruction(const Instruction *I) {
      return (isa<LoadInst>(I) && isa<AllocaInst>(I->getOperand(0))) ||
             (isa<StoreInst>(I) && isa<AllocaInst>(I->getOperand(1