lib/Transforms/Scalar/ScalarReplAggregates.cpp

   1 //===- ScalarReplAggregates.cpp - Scalar Replacement of Aggregates --------===//
   2 //
   3 // This transformation implements the well known scalar replacement of
   4 // aggregates transformation.  This xform breaks up alloca instructions of
   5 // aggregate type (structure or array) into individual alloca instructions for
   6 // each member (if possible).
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/Transforms/Scalar.h"
  11 #include "llvm/Function.h"
  12 #include "llvm/Pass.h"
  13 #include "llvm/iMemory.h"
  14 #include "llvm/DerivedTypes.h"
  15 #include "llvm/Constants.h"
  16 #include "Support/StringExtras.h"
  17 #include "Support/Statistic.h"
  18
  19 namespace {
  20   Statistic<> NumReplaced("scalarrepl", "Number of alloca's broken up");
  21
  22   struct SROA : public FunctionPass {
  23     bool runOnFunction(Function &F);
  24
  25   private:
  26     AllocaInst *AddNewAlloca(Function &F, const Type *Ty, AllocationInst *Base);
  27   };
  28
  29   RegisterOpt<SROA> X("scalarrepl", "Scalar Replacement of Aggregates");
  30 }
  31
  32 Pass *createScalarReplAggregatesPass() { return new SROA(); }
  33
  34
  35 // runOnFunction - This algorithm is a simple worklist driven algorithm, which
  36 // runs on all of the malloc/alloca instructions in the function, removing them
  37 // if they are only used by getelementptr instructions.
  38 //
  39 bool SROA::runOnFunction(Function &F) {
  40   std::vector<AllocationInst*> WorkList;
  41
  42   // Scan the entry basic block, adding any alloca's and mallocs to the worklist
  43   BasicBlock &BB = F.getEntryNode();
  44   for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
  45     if (AllocationInst *A = dyn_cast<AllocationInst>(I))
  46       WorkList.push_back(A);
  47
  48   // Process the worklist
  49   bool Changed = false;
  50   while (!WorkList.empty()) {
  51     AllocationInst *AI = WorkList.back();
  52     WorkList.pop_back();
  53
  54     // We cannot transform the allocation instruction if it is an array
  55     // allocation, and an allocation of a scalar value cannot be decomposed
  56     if (AI->isArrayAllocation() ||
  57         (!isa<StructType>(AI->getAllocatedType()) /*&&
  58                                                     !isa<ArrayType>(AI->getAllocatedType())*/
  59          )) continue;
  60
  61     // Loop over the use list of the alloca.  We can only transform it if there
  62     // are only getelementptr instructions (with a zero first index) and free
  63     // instructions.
  64     //
  65     bool CannotTransform = false;
  66     for (Value::use_iterator I = AI->use_begin(), E = AI->use_end();
  67          I != E; ++I) {
  68       Instruction *User = cast<Instruction>(*I);
  69       if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) {
  70         // The GEP is safe to transform if it is of the form GEP <ptr>, 0, <cst>
  71         if (GEPI->getNumOperands() <= 2 ||
  72             GEPI->getOperand(1) != Constant::getNullValue(Type::LongTy) ||
  73             !isa<Constant>(GEPI->getOperand(2)) ||
  74             isa<ConstantExpr>(GEPI->getOperand(2))) {
  75           DEBUG(std::cerr << "Cannot transform: " << *AI << "  due to user: "
  76                           << User);
  77           CannotTransform = true;
  78           break;
  79         }
  80       } else {
  81         DEBUG(std::cerr << "Cannot transform: " << *AI << "  due to user: "
  82                         << User);
  83         CannotTransform = true;
  84         break;
  85       }
  86     }
  87
  88     if (CannotTransform) continue;
  89
  90     DEBUG(std::cerr << "Found inst to xform: " << *AI);
  91     Changed = true;
  92
  93     std::vector<AllocaInst*> ElementAllocas;
  94     if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) {
  95       ElementAllocas.reserve(ST->getNumContainedTypes());
  96       for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) {
  97         AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0,
  98                                         AI->getName() + "." + utostr(i), AI);
  99         ElementAllocas.push_back(NA);
 100         WorkList.push_back(NA);  // Add to worklist for recursive processing
 101       }
 102     } else {
 103       const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType());
 104       ElementAllocas.reserve(AT->getNumElements());
 105       const Type *ElTy = AT->getElementType();
 106       for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) {
 107         AllocaInst *NA = new AllocaInst(ElTy, 0,
 108                                         AI->getName() + "." + utostr(i), AI);
 109         ElementAllocas.push_back(NA);
 110         WorkList.push_back(NA);  // Add to worklist for recursive processing
 111       }
 112     }
 113
 114     // Now that we have created the alloca instructions that we want to use,
 115     // expand the getelementptr instructions to use them.
 116     //
 117     for (Value::use_iterator I = AI->use_begin(), E = AI->use_end();
 118          I != E; ++I) {
 119       Instruction *User = cast<Instruction>(*I);
 120       if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) {
 121         // We now know that the GEP is of the form: GEP <ptr>, 0, <cst>
 122         uint64_t Idx;
 123         if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(GEPI->getOperand(2)))
 124           Idx = CSI->getValue();
 125         else
 126           Idx = cast<ConstantUInt>(GEPI->getOperand(2))->getValue();
 127
 128         assert(Idx < ElementAllocas.size() && "Index out of range?");
 129         AllocaInst *AllocaToUse = ElementAllocas[Idx];
 130
 131         Value *RepValue;
 132         if (GEPI->getNumOperands() == 3) {
 133           // Do not insert a new getelementptr instruction with zero indices,
 134           // only to have it optimized out later.
 135           RepValue = AllocaToUse;
 136         } else {
 137           // We are indexing deeply into the structure, so we still need a
 138           // getelement ptr instruction to finish the indexing.  This may be
 139           // expanded itself once the worklist is rerun.
 140           //
 141           std::string OldName = GEPI->getName();  // Steal the old name...
 142           GEPI->setName("");
 143           RepValue =
 144             new GetElementPtrInst(AllocaToUse,
 145                                   std::vector<Value*>(GEPI->op_begin()+3,
 146                                                       GEPI->op_end()),
 147                                   OldName, GEPI);
 148         }
 149
 150         // Move all of the users over to the new GEP.
 151         GEPI->replaceAllUsesWith(RepValue);
 152         // Delete the old GEP
 153         GEPI->getParent()->getInstList().erase(GEPI);
 154       } else {
 155         assert(0 && "Unexpected instruction type!");
 156       }
 157     }
 158
 159     // Finally, delete the Alloca instruction
 160     AI->getParent()->getInstList().erase(AI);
 161   }
 162
 163   return Changed;
 164 }