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 (or that have
// PHI nodes which are only loaded from).  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.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/PromoteMemToReg.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Instructions.h"
#include "llvm/Function.h"
#include "llvm/Constant.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/StableBasicBlockNumbering.h"
#include "llvm/ADT/StringExtras.h"
#include <algorithm>
using namespace llvm;

/// isAllocaPromotable - Return true if this alloca is legal for promotion.
/// This is true if there are only loads and stores to the alloca... of if there
/// is a PHI node using the address which can be trivially transformed.
///
bool llvm::isAllocaPromotable(const AllocaInst *AI, const TargetData &TD) {
  // 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 if (const PHINode *PN = dyn_cast<PHINode>(*UI)) {
      // We only support PHI nodes in a few simple cases.  The PHI node is only
      // allowed to have one use, which must be a load instruction, and can only
      // use alloca instructions (no random pointers).  Also, there cannot be
      // any accesses to AI between the PHI node and the use of the PHI.
      if (!PN->hasOneUse()) return false;

      // Our transformation causes the unconditional loading of all pointer
      // operands to the PHI node.  Because this could cause a fault if there is
      // a critical edge in the CFG and if one of the pointers is illegal, we
      // refuse to promote PHI nodes unless they are obviously safe.  For now,
      // obviously safe means that all of the operands are allocas.
      //
      // If we wanted to extend this code to break critical edges, this
      // restriction could be relaxed, and we could even handle uses of the PHI
      // node that are volatile loads or stores.
      //
      for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
        if (!isa<AllocaInst>(PN->getIncomingValue(i)))
          return false;
      
      // Now make sure the one user instruction is in the same basic block as
      // the PHI, and that there are no loads or stores between the PHI node and
      // the access.
      BasicBlock::const_iterator UI = cast<Instruction>(PN->use_back());
      if (!isa<LoadInst>(UI) || cast<LoadInst>(UI)->isVolatile()) return false;
      
      // Scan looking for memory accesses.
      // FIXME: this should REALLY use alias analysis.
      for (--UI; !isa<PHINode>(UI); --UI)
        if (isa<LoadInst>(UI) || isa<StoreInst>(UI) || isa<CallInst>(UI))
          return false;

      // If we got this far, we can promote the PHI use.
    } else if (const SelectInst *SI = dyn_cast<SelectInst>(*UI)) {
      // We only support selects in a few simple cases.  The select is only
      // allowed to have one use, which must be a load instruction, and can only
      // use alloca instructions (no random pointers).  Also, there cannot be
      // any accesses to AI between the PHI node and the use of the PHI.
      if (!SI->hasOneUse()) return false;

      // Our transformation causes the unconditional loading of all pointer
      // operands of the select.  Because this could cause a fault if there is a
      // critical edge in the CFG and if one of the pointers is illegal, we
      // refuse to promote the select unless it is obviously safe.  For now,
      // obviously safe means that all of the operands are allocas.
      //
      if (!isa<AllocaInst>(SI->getOperand(1)) ||
          !isa<AllocaInst>(SI->getOperand(2)))
        return false;
      
      // Now make sure the one user instruction is in the same basic block as
      // the PHI, and that there are no loads or stores between the PHI node and
      // the access.
      BasicBlock::const_iterator UI = cast<Instruction>(SI->use_back());
      if (!isa<LoadInst>(UI) || cast<LoadInst>(UI)->isVolatile()) return false;
      
      // Scan looking for memory accesses.
      // FIXME: this should REALLY use alias analysis.
      for (--UI; &*UI != SI; --UI)
        if (isa<LoadInst>(UI) || isa<StoreInst>(UI) || isa<CallInst>(UI))
          return false;

      // If we got this far, we can promote the select use.
    } else {
      return false;   // Not a load, store, or promotable PHI?
    }
  
  return true;
}

namespace {
  struct PromoteMem2Reg {
    // Allocas - The alloca instructions being promoted
    std::vector<AllocaInst*> Allocas;
    DominatorTree &DT;
    DominanceFrontier &DF;
    const TargetData &TD;

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

    // NewPhiNodes - The PhiNodes we're adding.
    std::map<BasicBlock*, std::vector<PHINode*> > NewPhiNodes;

    // Visited - The set of basic blocks the renamer has already visited.
    std::set<BasicBlock*> Visited;

    // BBNumbers - Contains a stable numbering of basic blocks to avoid
    // non-determinstic behavior.
    StableBasicBlockNumbering BBNumbers;

  public:
    PromoteMem2Reg(const std::vector<AllocaInst*> &A, DominatorTree &dt,
                   DominanceFrontier &df, const TargetData &td)
      : Allocas(A), DT(dt), DF(df), TD(td) {}

    void run();

  private:
    void MarkDominatingPHILive(BasicBlock *BB, unsigned AllocaNum,
                               std::set<PHINode*> &DeadPHINodes);
    void PromoteLocallyUsedAlloca(BasicBlock *BB, AllocaInst *AI);
    void PromoteLocallyUsedAllocas(BasicBlock *BB, 
                                   const std::vector<AllocaInst*> &AIs);

    void RenamePass(BasicBlock *BB, BasicBlock *Pred,
                    std::vector<Value*> &IncVals);
    bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version,
                      std::set<PHINode*> &InsertedPHINodes);
  };
}  // end of anonymous namespace

void PromoteMem2Reg::run() {
  Function &F = *DF.getRoot()->getParent();

  // LocallyUsedAllocas - Keep track of all of the alloca instructions which are
  // only used in a single basic block.  These instructions can be efficiently
  // promoted by performing a single linear scan over that one block.  Since
  // individual basic blocks are sometimes large, we group together all allocas
  // that are live in a single basic block by the basic block they are live in.
  std::map<BasicBlock*, std::vector<AllocaInst*> > LocallyUsedAllocas;


  for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
    AllocaInst