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