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 isSafeArrayElementUse(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;
 107         if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(GEPI->getOperand(2)))
 108           Idx = CSI->getValue();
 109         else
 110           Idx = cast<ConstantUInt>(GEPI->getOperand(2))->getValue();
 111
 112         assert(Idx < ElementAllocas.size() && "Index out of range?");
 113         AllocaInst *AllocaToUse = ElementAllocas[Idx];
 114
 115         Value *RepValue;
 116         if (GEPI->getNumOperands() == 3) {
 117           // Do not insert a new getelementptr instruction with zero indices,
 118           // only to have it optimized out later.
 119           RepValue = AllocaToUse;
 120         } else {
 121           // We are indexing deeply into the structure, so we still need a
 122           // getelement ptr instruction to finish the indexing.  This may be
 123           // expanded itself once the worklist is rerun.
 124           //
 125           std::string OldName = GEPI->getName();  // Steal the old name...
 126           std::vector<Value*> NewArgs;
 127           NewArgs.push_back(Constant::getNullValue(Type::LongTy));
 128           NewArgs.insert(NewArgs.end(), GEPI->op_begin()+3, GEPI->op_end());
 129           GEPI->setName("");
 130           RepValue =
 131             new GetElementPtrInst(AllocaToUse, NewArgs, OldName, GEPI);
 132         }
 133
 134         // Move all of the users over to the new GEP.
 135         GEPI->replaceAllUsesWith(RepValue);
 136         // Delete the old GEP
 137         GEPI->getParent()->getInstList().erase(GEPI);
 138       } else {
 139         assert(0 && "Unexpected instruction type!");
 140       }
 141     }
 142
 143     // Finally, delete the Alloca instruction
 144     AI->getParent()->getInstList().erase(AI);
 145     NumReplaced++;
 146   }
 147
 148   return Changed;
 149 }
 150
 151
 152 /// isSafeUseOfAllocation - Check to see if this user is an allowed use for an
 153 /// aggregate allocation.
 154 ///
 155 bool SROA::isSafeUseOfAllocation(Instruction *User) {
 156   if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) {
 157     // The GEP is safe to transform if it is of the form GEP <ptr>, 0, <cst>
 158     if (GEPI->getNumOperands() <= 2 ||
 159         GEPI->getOperand(1) != Constant::getNullValue(Type::LongTy) ||
 160         !isa<Constant>(GEPI->getOperand(2)) ||
 161         isa<ConstantExpr>(GEPI->getOperand(2)))
 162       return false;
 163   } else {
 164     return false;
 165   }
 166   return true;
 167 }
 168
 169
 170 /// isSafeArrayElementUse - Check to see if this use is an allowed use for a
 171 /// getelementptr instruction of an array aggregate allocation.
 172 ///
 173 bool SROA::isSafeArrayElementUse(Value *Ptr) {
 174   for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end();
 175        I != E; ++I) {
 176     Instruction *User = cast<Instruction>(*I);
 177     switch (User->getOpcode()) {
 178     case Instruction::Load:  return true;
 179     case Instruction::Store: return User->getOperand(0) != Ptr;
 180     case Instruction::GetElementPtr: {
 181       GetElementPtrInst *GEP = cast<GetElementPtrInst>(User);
 182       if (GEP->getNumOperands() > 1) {
 183         if (!isa<Constant>(GEP->getOperand(1)) ||
 184             !cast<Constant>(GEP->getOperand(1))->isNullValue())
 185           return false;  // Using pointer arithmetic to navigate the array...
 186
 187         // Check to see if there are any structure indexes involved in this GEP.
 188         // If so, then we can safely break the array up until at least the
 189         // structure.
 190         for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i)
 191           if (GEP->getOperand(i)->getType()->isUnsigned())
 192             break;
 193       }
 194       return isSafeArrayElementUse(GEP);
 195     }
 196     default:
 197       DEBUG(std::cerr << "  Transformation preventing inst: " << *User);
 198       return false;
 199     }
 200   }
 201   return true;  // All users look ok :)
 202 }
 203
 204
 205 /// isSafeStructAllocaToPromote - Check to see if the specified allocation of a
 206 /// structure can be broken down into elements.
 207 ///
 208 bool SROA::isSafeStructAllocaToPromote(AllocationInst *AI) {
 209   // Loop over the use list of the alloca.  We can only transform it if all of
 210   // the users are safe to transform.
 211   //
 212   for (Value::use_iterator I = AI->use_begin(), E = AI->use_end();
 213        I != E; ++I)
 214     if (!isSafeUseOfAllocation(cast<Instruction>(*I))) {
 215       DEBUG(std::cerr << "Cannot transform: " << *AI << "  due to user: "
 216                       << *I);
 217       return false;
 218     }
 219   return true;
 220 }
 221
 222
 223 /// isSafeArrayAllocaToPromote - Check to see if the specified allocation of a
 224 /// structure can be broken down into elements.
 225 ///
 226 bool SROA::isSafeArrayAllocaToPromote(AllocationInst *AI) {
 227   const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType());
 228   int64_t NumElements = AT->getNumElements();
 229
 230   // Loop over the use list of the alloca.  We can only transform it if all of
 231   // the users are safe to transform.  Array allocas have extra constraints to
 232   // meet though.
 233   //
 234   for (Value::use_iterator I = AI->use_begin(), E = AI->use_end();
 235        I != E; ++I) {
 236     Instruction *User = cast<Instruction>(*I);
 237     if (!isSafeUseOfAllocation(User)) {
 238       DEBUG(std::cerr << "Cannot transform: " << *AI << "  due to user: "
 239                       << User);
 240       return false;
 241     }
 242
 243     // Check to make sure that getelementptr follow the extra rules for arrays:
 244     if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) {
 245       // Check to make sure that index falls within the array.  If not,
 246       // something funny is going on, so we won't do the optimization.
 247       //
 248       if (cast<ConstantSInt>(GEPI->getOperand(2))->getValue() >= NumElements)
 249         return false;
 250
 251       // Check to make sure that the only thing that uses the resultant pointer
 252       // is safe for an array access.  For example, code that looks like:
 253       //   P = &A[0];  P = P + 1
 254       // is legal, and should prevent promotion.
 255       //
 256       if (!isSafeArrayElementUse(GEPI)) {
 257         DEBUG(std::cerr << "Cannot transform: " << *AI
 258                         << "  due to uses of user: " << *GEPI);
 259         return false;
 260       }
 261     }
 262   }
 263   return true;
 264 }
 265