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