lib/Transforms/Utils/PromoteMemoryToRegister.cpp

   1 //===- PromoteMemoryToRegister.cpp - Convert memory refs to regs ----------===//
   2 //
   3 // This pass is used to promote memory references to be register references.  A
   4 // simple example of the transformation performed by this pass is:
   5 //
   6 //        FROM CODE                           TO CODE
   7 //   %X = alloca int, uint 1                 ret int 42
   8 //   store int 42, int *%X
   9 //   %Y = load int* %X
  10 //   ret int %Y
  11 //
  12 // To do this transformation, a simple analysis is done to ensure it is safe.
  13 // Currently this just loops over all alloca instructions, looking for
  14 // instructions that are only used in simple load and stores.
  15 //
  16 // After this, the code is transformed by...
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #include "llvm/Transforms/Scalar/PromoteMemoryToRegister.h"
  21 #include "llvm/Analysis/Dominators.h"
  22 #include "llvm/iMemory.h"
  23 #include "llvm/Pass.h"
  24 #include "llvm/Method.h"
  25 #include "llvm/BasicBlock.h"
  26 #include "llvm/Assembly/Writer.h"  // For debugging
  27 using cfg::DominanceFrontier;
  28
  29 // PromotePass - This class is implements the PromoteMemoryToRegister pass
  30 //
  31 class PromotePass : public MethodPass {
  32 public:
  33   // runOnMethod - To run this pass, first we calculate the alloca instructions
  34   // that are safe for promotion, then we promote each one.
  35   //
  36   virtual bool runOnMethod(Method *M) {
  37     std::vector<AllocaInst*> Allocas;
  38     findSafeAllocas(M, Allocas);      // Calculate safe allocas
  39
  40     // Get dominance frontier information...
  41     DominanceFrontier &DF = getAnalysis<DominanceFrontier>();
  42
  43     // Transform each alloca in turn...
  44     for (std::vector<AllocaInst*>::iterator I = Allocas.begin(),
  45            E = Allocas.end(); I != E; ++I)
  46       promoteAlloca(*I, DF);
  47
  48     return !Allocas.empty();
  49   }
  50
  51
  52   // getAnalysisUsageInfo - We need dominance frontiers
  53   //
  54   virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
  55                                     Pass::AnalysisSet &Destroyed,
  56                                     Pass::AnalysisSet &Provided) {
  57     Requires.push_back(DominanceFrontier::ID);
  58   }
  59
  60 private:
  61   // findSafeAllocas - Find allocas that are safe to promote
  62   //
  63   void findSafeAllocas(Method *M, std::vector<AllocaInst*> &Allocas) const;
  64
  65   // promoteAlloca - Convert the use chain of an alloca instruction into
  66   // register references.
  67   //
  68   void promoteAlloca(AllocaInst *AI, DominanceFrontier &DF);
  69 };
  70
  71
  72 // findSafeAllocas - Find allocas that are safe to promote
  73 //
  74 void PromotePass::findSafeAllocas(Method *M,
  75                                   std::vector<AllocaInst*> &Allocas) const {
  76   BasicBlock *BB = M->front();  // Get the entry node for the method
  77
  78   // Look at all instructions in the entry node
  79   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
  80     if (AllocaInst *AI = dyn_cast<AllocaInst>(*I))       // Is it an alloca?
  81       if (!AI->isArrayAllocation()) {
  82         bool isSafe = true;
  83         for (Value::use_iterator UI = AI->use_begin(), UE = AI->use_end();
  84              UI != UE; ++UI) {   // Loop over all of the uses of the alloca
  85           // Only allow nonindexed memory access instructions...
  86           if (MemAccessInst *MAI = dyn_cast<MemAccessInst>(*UI)) {
  87             if (MAI->hasIndices()) { isSafe = false; break; } // indexed?
  88           } else {
  89             isSafe = false; break;   // Not a load or store?
  90           }
  91         }
  92
  93         if (isSafe)              // If all checks pass, add alloca to safe list
  94           Allocas.push_back(AI);
  95       }
  96
  97 }
  98
  99
 100
 101 // promoteAlloca - Convert the use chain of an alloca instruction into
 102 // register references.
 103 //
 104 void PromotePass::promoteAlloca(AllocaInst *AI, DominanceFrontier &DFInfo) {
 105   std::cerr << "TODO: Should process: " << AI;
 106 }
 107
 108
 109 // newPromoteMemoryToRegister - Provide an entry point to create this pass.
 110 //
 111 Pass *newPromoteMemoryToRegister() {
 112   return new PromotePass();
 113 }