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     bool isSafeElementUse(Value *Ptr);
  27     bool isSafeUseOfAllocation(Instruction *User);
  28     bool isSafeStructAllocaToPromote(AllocationInst *AI);
  29     bool isSafeArrayAllocaToPromote(AllocationInst *AI);
  30     AllocaInst *AddNewAlloca(Function &F, const Type *Ty, AllocationInst *Base);
  31   };
  32
  33   RegisterOpt<SROA> X("scalarrepl", "Scalar Replacement of Aggregates");
  34 }
  35
  36 Pass *createScalarReplAggregatesPass() { return new SROA(); }
  37
  38
  39 // runOnFunction - This algorithm is a simple worklist driven algorithm, which
  40 // runs on all of the malloc/alloca instructions in the function, removing them
  41 // if they are only used by getelementptr instructions.
  42 //
  43 bool SROA::runOnFunction(Function &F) {
  44   std::vector<AllocationInst*> WorkList;
  45
  46   // Scan the entry basic block, adding any alloca's and mallocs to the worklist
  47   BasicBlock &BB = F.getEntryNode();
  48   for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
  49     if (AllocationInst *A = dyn_cast<AllocationInst>(I))
  50       WorkList.push_back(A);
  51
  52   // Process the worklist
  53   bool Changed = false;
  54   while (!WorkList.empty()) {
  55     AllocationInst *AI = WorkList.back();
  56     WorkList.pop_back();
  57
  58     // We cannot transform the allocation instruction if it is an array
  59     // allocation (allocations OF arrays are ok though), and an allocation of a
  60     // scalar value cannot be decomposed at all.
  61     //
  62     if (AI->isArrayAllocation() ||
  63         (!isa<StructType>(AI->getAllocatedType()) &&
  64          !isa<ArrayType>(AI->getAllocatedType()))) continue;
  65
  66     // Check that all of the users of the allocation are capable of being
  67     // transformed.
  68     if (isa<StructType>(AI->getAllocatedType())) {
  69       if (!isSafeStructAllocaToPromote(AI))
  70         continue;
  71     } else if (!isSafeArrayAllocaToPromote(AI))
  72       continue;
  73
  74     DEBUG(std::cerr << "Found inst to xform: " << *AI);
  75     Changed = true;
  76
  77     std::vector<AllocaInst*> ElementAllocas;
  78     if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) {
  79       ElementAllocas.reserve(ST->getNumContainedTypes());
  80       for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) {
  81         AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0,
  82                                         AI->getName() + "." + utostr(i), AI);
  83         ElementAllocas.push_back(NA);
  84         WorkList.push_back(NA);  // Add to worklist for recursive processing
  85       }
  86     } else {
  87       const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType());
  88       ElementAllocas.reserve(AT->getNumElements());
  89       const Type *ElTy = AT->getElementType();
  90       for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) {
  91         AllocaInst *NA = new AllocaInst(ElTy, 0,
  92                                         AI->getName() + "." + utostr(i), AI);
  93         ElementAllocas.push_back(NA);
  94         WorkList.push_back(NA);  // Add to worklist for recursive processing
  95       }
  96     }
  97
  98     // Now that we have created the alloca instructions that we want to use,
  99     // expand the getelementptr instructions to use them.
 100     //
 101     for (Value::use_iterator I = AI->use_begin(), E = AI->use_end();
 102          I != E; ++I) {
 103       Instruction *User = cast<Instruction>(*I);
 104       if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) {
 105         // We now know that the GEP is of the form: GEP <ptr>, 0, <cst>
 106         uint64_t Idx = cast<ConstantInt>(GEPI->getOperand(2))->getRawValue();
 107
 108         assert(Idx < ElementAllocas.size() && "Index out of range?");
 109         AllocaInst *AllocaToUse = ElementAllocas[Idx];
 110
 111         Value *RepValue;
 112         if (GEPI->getNumOperands() == 3) {
 113           // Do not insert a new getelementptr instruction with zero indices,
 114           // only to have it optimized out later.
 115           RepValue = AllocaToUse;
 116         } else {
 117           // We are indexing deeply into the structure, so we still need a
 118           // getelement ptr instruction to finish the indexing.  This may be
 119           // expanded itself once the worklist is rerun.
 120           //
 121           std::string OldName = GEPI->getName();  // Steal the old name...
 122           std::vector<Value*> NewArgs;
 123           NewArgs.push_back(Constant::getNullValue(Type::LongTy));
 124           NewArgs.insert(NewArgs.end(), GEPI->op_begin()+3, GEPI->op_end());
 125           GEPI->setName("");
 126           RepValue =
 127             new GetElementPtrInst(AllocaToUse, NewArgs, OldName, GEPI);
 128         }
 129
 130         // Move all of the users over to the new GEP.
 131         GEPI->replaceAllUsesWith(RepValue);
 132         // Delete the old GEP
 133         GEPI->getParent()->getInstList().erase(GEPI);
 134       } else {
 135         assert(0 && "Unexpected instruction type!");
 136       }
 137     }
 138
 139     // Finally, delete the Alloca instruction
 140     AI->getParent()->getInstList().erase(AI);
 141     NumReplaced++;
 142   }
 143
 144   return Changed;
 145 }
 146
 147
 148 /// isSafeUseOfAllocation - Check to see if this user is an allowed use for an
 149 /// aggregate allocation.
 150 ///
 151 bool SROA::isSafeUseOfAllocation(Instruction *User) {
 152   if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) {
 153     // The GEP is safe to transform if it is of the form GEP <ptr>, 0, <cst>
 154     if (GEPI->getNumOperands() <= 2 ||
 155         GEPI->getOperand(1) != Constant::getNullValue(Type::LongTy) ||
 156         !isa<Constant>(GEPI->getOperand(2)) ||
 157         isa<ConstantExpr>(GEPI->getOperand(2)))
 158       return false;
 159   } else {
 160     return false;
 161   }
 162   return true;
 163 }
 164
 165 /// isSafeElementUse - Check to see if this use is an allowed use for a
 166 /// getelementptr instruction of an array aggregate allocation.
 167 ///
 168 bool SROA::isSafeElementUse(Value *Ptr) {
 169   for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end();
 170        I != E; ++I) {
 171     Instruction *User = cast<Instruction>(*I);
 172     switch (User->getOpcode()) {
 173     case Instruction::Load:  return true;
 174     case Instruction::Store: return User->getOperand(0) != Ptr;
 175     case Instruction::GetElementPtr: {
 176       GetElementPtrInst *GEP = cast<GetElementPtrInst>(User);
 177       if (GEP->getNumOperands() > 1) {
 178         if (!isa<Constant>(GEP->getOperand(1)) ||
 179             !cast<Constant>(GEP->getOperand(1))->isNullValue())
 180           return false;  // Using pointer arithmetic to navigate the array...
 181       }
 182       return isSafeElementUse(GEP);
 183     }
 184     default:
 185       DEBUG(std::cerr << "  Transformation preventing inst: " << *User);
 186       return false;
 187     }
 188   }
 189   return true;  // All users look ok :)
 190 }
 191
 192
 193 /// isSafeStructAllocaToPromote - Check to see if the specified allocation of a
 194 /// structure can be broken down into elements.
 195 ///
 196 bool SROA::isSafeStructAllocaToPromote(AllocationInst *AI) {
 197   // Loop over the use list of the alloca.  We can only transform it if all of
 198   // the users are safe to transform.
 199   //
 200   for (Value::use_iterator I = AI->use_begin(), E = AI->use_end();
 201        I != E; ++I) {
 202     if (!isSafeUseOfAllocation(cast<Instruction>(*I))) {
 203       DEBUG(std::cerr << "Cannot transform: " << *AI << "  due to user: "
 204                       << *I);
 205       return false;
 206     }
 207
 208     // Pedantic check to avoid breaking broken programs...
 209     if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*I))
 210       if (GEPI->getNumOperands() == 3 && !isSafeElementUse(GEPI))
 211         return false;
 212   }
 213   return true;
 214 }
 215
 216
 217 /// isSafeArrayAllocaToPromote - Check to see if the specified allocation of a
 218 /// structure can be broken down into elements.
 219 ///
 220 bool SROA::isSafeArrayAllocaToPromote(AllocationInst *AI) {
 221   const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType());
 222   int64_t NumElements = AT->getNumElements();
 223
 224   // Loop over the use list of the alloca.  We can only transform it if all of
 225   // the users are safe to transform.  Array allocas have extra constraints to
 226   // meet though.
 227   //
 228   for (Value::use_iterator I = AI->use_begin(), E = AI->use_end();
 229        I != E; ++I) {
 230     Instruction *User = cast<Instruction>(*I);
 231     if (!isSafeUseOfAllocation(User)) {
 232       DEBUG(std::cerr << "Cannot transform: " << *AI << "  due to user: "
 233                       << User);
 234       return false;
 235     }
 236
 237     // Check to make sure that getelementptr follow the extra rules for arrays:
 238     if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) {
 239       // Check to make sure that index falls within the array.  If not,
 240       // something funny is going on, so we won't do the optimization.
 241       //
 242       if (cast<ConstantSInt>(GEPI->getOperand(2))->getValue() >= NumElements)
 243         return false;
 244
 245       // Check to make sure that the only thing that uses the resultant pointer
 246       // is safe for an array access.  For example, code that looks like:
 247       //   P = &A[0];  P = P + 1
 248       // is legal, and should prevent promotion.
 249       //
 250       if (!isSafeElementUse(GEPI)) {
 251         DEBUG(std::cerr << "Cannot transform: " << *AI
 252                         << "  due to uses of user: " << *GEPI);
 253         return false;
 254       }
 255     }
 256   }
 257   return true;
 258 }
 259