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

//===- PromoteMemoryToRegister.cpp - Convert allocas to registers ---------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file promote 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/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/StringExtras.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.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");

// Provide DenseMapKeyInfo for all pointers.
namespace llvm {
template<>
struct DenseMapKeyInfo<std::pair<BasicBlock*, unsigned> > {
  static inline std::pair<BasicBlock*, unsigned> getEmptyKey() {
    return std::make_pair((BasicBlock*)-1, ~0U);
  }
  static inline std::pair<BasicBlock*, unsigned> getTombstoneKey() {
    return std::make_pair((BasicBlock*)-2, 0U);
  }
  static unsigned getHashValue(const std::pair<BasicBlock*, unsigned> &Val) {
    return DenseMapKeyInfo<void*>::getHashValue(Val.first) + Val.second*2;
  }
  static bool isPod() { return true; }
};
}

/// 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 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 (isa<LoadInst>(*UI)) {
      // noop
    } 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.
    } else {
      return false;   // Not a load or store.
    }

  return true;
}

namespace {
  struct AllocaInfo;

  // Data package used by RenamePass()
  class VISIBILITY_HIDDEN RenamePassData {
  public:
    typedef std::vector<Value *> ValVector;
    
    RenamePassData() {}
    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);
    }
  };

  struct VISIBILITY_HIDDEN PromoteMem2Reg {
    /// Allocas - The alloca instructions being promoted.
    ///
    std::vector<AllocaInst*> Allocas;
    SmallVector<AllocaInst*, 16> &RetryList;
    DominatorTree &DT;
    DominanceFrontier &DF;

    /// AST - An AliasSetTracker object to update.  If null, don't update it.
    ///
    AliasSetTracker *AST;

    /// AllocaLookup - Reverse mapping of Allocas.
    ///
    std::map<AllocaInst*, unsigned>  AllocaLookup;

    /// NewPhiNodes - The PhiNodes we're adding.
    ///
    DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*> NewPhiNodes;
    
    /// PhiToAllocaMap - For each PHI node, keep track of which entry in Allocas
    /// it corresponds to.
    DenseMap<PHINode*, unsigned> PhiToAllocaMap;
    
    /// PointerAllocaValues - If we are updating an AliasSetTracker, then for
    /// each alloca that is of pointer type, we keep track of what to copyValue
    /// to the inserted PHI nodes here.
    ///
    std::vector<Value*> PointerAllocaValues;

    /// Visited - The set of basic blocks the renamer has already visited.
    ///
    SmallPtrSet<BasicBlock*, 16> Visited;

    /// BBNumbers - Contains a stable numbering of basic blocks to avoid
    /// non-determinstic behavior.
    DenseMap<BasicBlock*, unsigned> BBNumbers;

    /// BBNumPreds - Lazily compute the number of predecessors a block has.
    DenseMap<const BasicBlock*, unsigned> BBNumPreds;
  public:
    PromoteMem2Reg(const