lib/Transforms/Scalar/DecomposeMultiDimRefs.cpp

   1 //===- llvm/Transforms/DecomposeMultiDimRefs.cpp - Lower array refs to 1D -===//
   2 //
   3 // DecomposeMultiDimRefs - Convert multi-dimensional references consisting of
   4 // any combination of 2 or more array and structure indices into a sequence of
   5 // instructions (using getelementpr and cast) so that each instruction has at
   6 // most one index (except structure references, which need an extra leading
   7 // index of [0]).
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #include "llvm/Transforms/Scalar/DecomposeMultiDimRefs.h"
  12 #include "llvm/Constants.h"
  13 #include "llvm/iMemory.h"
  14 #include "llvm/iOther.h"
  15 #include "llvm/BasicBlock.h"
  16 #include "llvm/Function.h"
  17 #include "llvm/Pass.h"
  18
  19 namespace {
  20   struct DecomposePass : public BasicBlockPass {
  21     virtual bool runOnBasicBlock(BasicBlock *BB);
  22
  23   private:
  24     static void decomposeArrayRef(BasicBlock::iterator &BBI);
  25   };
  26 }
  27
  28 Pass *createDecomposeMultiDimRefsPass() {
  29   return new DecomposePass();
  30 }
  31
  32
  33 // runOnBasicBlock - Entry point for array or structure references with multiple
  34 // indices.
  35 //
  36 bool DecomposePass::runOnBasicBlock(BasicBlock *BB) {
  37   bool Changed = false;
  38   for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ) {
  39     if (MemAccessInst *MAI = dyn_cast<MemAccessInst>(*II)) {
  40       if (MAI->getNumOperands() > MAI->getFirstIndexOperandNumber()+1) {
  41         decomposeArrayRef(II);
  42         Changed = true;
  43       } else {
  44         ++II;
  45       }
  46     } else {
  47       ++II;
  48     }
  49   }
  50
  51   return Changed;
  52 }
  53
  54 //
  55 // For any combination of 2 or more array and structure indices,
  56 // this function repeats the foll. until we have a one-dim. reference: {
  57 //      ptr1 = getElementPtr [CompositeType-N] * lastPtr, uint firstIndex
  58 //      ptr2 = cast [CompositeType-N] * ptr1 to [CompositeType-N] *
  59 // }
  60 // Then it replaces the original instruction with an equivalent one that
  61 // uses the last ptr2 generated in the loop and a single index.
  62 // If any index is (uint) 0, we omit the getElementPtr instruction.
  63 //
  64 void DecomposePass::decomposeArrayRef(BasicBlock::iterator &BBI) {
  65   MemAccessInst *MAI = cast<MemAccessInst>(*BBI);
  66   BasicBlock *BB = MAI->getParent();
  67   Value *LastPtr = MAI->getPointerOperand();
  68
  69   // Remove the instruction from the stream
  70   BB->getInstList().remove(BBI);
  71
  72   vector<Instruction*> NewInsts;
  73
  74   // Process each index except the last one.
  75   //
  76   User::const_op_iterator OI = MAI->idx_begin(), OE = MAI->idx_end();
  77   for (; OI+1 != OE; ++OI) {
  78     assert(isa<PointerType>(LastPtr->getType()));
  79
  80     // Check for a zero index.  This will need a cast instead of
  81     // a getElementPtr, or it may need neither.
  82     bool indexIsZero = isa<ConstantUInt>(*OI) &&
  83                        cast<Constant>(*OI)->isNullValue();
  84
  85     // Extract the first index.  If the ptr is a pointer to a structure
  86     // and the next index is a structure offset (i.e., not an array offset),
  87     // we need to include an initial [0] to index into the pointer.
  88     //
  89     vector<Value*> Indices;
  90     PointerType *PtrTy = cast<PointerType>(LastPtr->getType());
  91     if (isa<StructType>(PtrTy->getElementType())
  92         && !PtrTy->indexValid(*OI))
  93       Indices.push_back(Constant::getNullValue(Type::UIntTy));
  94     Indices.push_back(*OI);
  95
  96     // Get the type obtained by applying the first index.
  97     // It must be a structure or array.
  98     const Type *NextTy = MemAccessInst::getIndexedType(LastPtr->getType(),
  99                                                        Indices, true);
 100     assert(isa<CompositeType>(NextTy));
 101
 102     // Get a pointer to the structure or to the elements of the array.
 103     const Type *NextPtrTy =
 104       PointerType::get(isa<StructType>(NextTy) ? NextTy
 105                        : cast<ArrayType>(NextTy)->getElementType());
 106
 107     // Instruction 1: nextPtr1 = GetElementPtr LastPtr, Indices
 108     // This is not needed if the index is zero.
 109     if (!indexIsZero) {
 110       LastPtr = new GetElementPtrInst(LastPtr, Indices, "ptr1");
 111       NewInsts.push_back(cast<Instruction>(LastPtr));
 112     }
 113
 114     // Instruction 2: nextPtr2 = cast nextPtr1 to NextPtrTy
 115     // This is not needed if the two types are identical.
 116     //
 117     if (LastPtr->getType() != NextPtrTy) {
 118       LastPtr = new CastInst(LastPtr, NextPtrTy, "ptr2");
 119       NewInsts.push_back(cast<Instruction>(LastPtr));
 120     }
 121   }
 122
 123   //
 124   // Now create a new instruction to replace the original one
 125   //
 126   PointerType *PtrTy = cast<PointerType>(LastPtr->getType());
 127
 128   // First, get the final index vector.  As above, we may need an initial [0].
 129   vector<Value*> Indices;
 130   if (isa<StructType>(PtrTy->getElementType())
 131       && !PtrTy->indexValid(*OI))
 132     Indices.push_back(Constant::getNullValue(Type::UIntTy));
 133
 134   Indices.push_back(*OI);
 135
 136   Instruction *NewI = 0;
 137   switch(MAI->getOpcode()) {
 138   case Instruction::Load:
 139     NewI = new LoadInst(LastPtr, Indices, MAI->getName());
 140     break;
 141   case Instruction::Store:
 142     NewI = new StoreInst(MAI->getOperand(0), LastPtr, Indices);
 143     break;
 144   case Instruction::GetElementPtr:
 145     NewI = new GetElementPtrInst(LastPtr, Indices, MAI->getName());
 146     break;
 147   default:
 148     assert(0 && "Unrecognized memory access instruction");
 149   }
 150   NewInsts.push_back(NewI);
 151
 152   // Replace all uses of the old instruction with the new
 153   MAI->replaceAllUsesWith(NewI);
 154
 155   // Now delete the old instruction...
 156   delete MAI;
 157
 158   // Convert our iterator into an index... that cannot get invalidated
 159   unsigned ItOffs = BBI-BB->begin();
 160
 161   // Insert all of the new instructions...
 162   BB->getInstList().insert(BBI, NewInsts.begin(), NewInsts.end());
 163
 164   // Advance the iterator to the instruction following the one just inserted...
 165   BBI = BB->begin() + ItOffs + NewInsts.size();
 166 }