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.h"
  12 #include "llvm/DerivedTypes.h"
  13 #include "llvm/Constants.h"
  14 #include "llvm/Constant.h"
  15 #include "llvm/iMemory.h"
  16 #include "llvm/iOther.h"
  17 #include "llvm/BasicBlock.h"
  18 #include "llvm/Pass.h"
  19 #include "Support/StatisticReporter.h"
  20
  21 static Statistic<> NumAdded("lowerrefs\t\t- New instructions added");
  22
  23 namespace {
  24   struct DecomposePass : public BasicBlockPass {
  25     virtual bool runOnBasicBlock(BasicBlock &BB);
  26
  27   private:
  28     static bool decomposeArrayRef(BasicBlock::iterator &BBI);
  29   };
  30
  31   RegisterOpt<DecomposePass> X("lowerrefs", "Decompose multi-dimensional "
  32                                "structure/array references");
  33 }
  34
  35 Pass
  36 *createDecomposeMultiDimRefsPass()
  37 {
  38   return new DecomposePass();
  39 }
  40
  41
  42 // runOnBasicBlock - Entry point for array or structure references with multiple
  43 // indices.
  44 //
  45 bool
  46 DecomposePass::runOnBasicBlock(BasicBlock &BB)
  47 {
  48   bool Changed = false;
  49   for (BasicBlock::iterator II = BB.begin(); II != BB.end(); ) {
  50     if (MemAccessInst *MAI = dyn_cast<MemAccessInst>(&*II))
  51       if (MAI->getNumIndices() >= 2) {
  52         Changed = decomposeArrayRef(II) || Changed; // always modifies II
  53         continue;
  54       }
  55     ++II;
  56   }
  57   return Changed;
  58 }
  59
  60 // Check for a constant (uint) 0.
  61 inline bool
  62 IsZero(Value* idx)
  63 {
  64   return (isa<ConstantInt>(idx) && cast<ConstantInt>(idx)->isNullValue());
  65 }
  66
  67 // For any MemAccessInst with 2 or more array and structure indices:
  68 //
  69 //      opCode CompositeType* P, [uint|ubyte] idx1, ..., [uint|ubyte] idxN
  70 //
  71 // this function generates the foll sequence:
  72 //
  73 //      ptr1   = getElementPtr P,         idx1
  74 //      ptr2   = getElementPtr ptr1,   0, idx2
  75 //      ...
  76 //      ptrN-1 = getElementPtr ptrN-2, 0, idxN-1
  77 //      opCode                 ptrN-1, 0, idxN  // New-MAI
  78 //
  79 // Then it replaces the original instruction with this sequence,
  80 // and replaces all uses of the original instruction with New-MAI.
  81 // If idx1 is 0, we simply omit the first getElementPtr instruction.
  82 //
  83 // On return: BBI points to the instruction after the current one
  84 //            (whether or not *BBI was replaced).
  85 //
  86 // Return value: true if the instruction was replaced; false otherwise.
  87 //
  88 bool
  89 DecomposePass::decomposeArrayRef(BasicBlock::iterator &BBI)
  90 {
  91   // FIXME: If condition below
  92   MemAccessInst &MAI = cast<MemAccessInst>(*BBI);
  93   // FIXME: If condition below
  94
  95   // If this instr has no indexes, then the decomposed version is identical to
  96   // the instruction itself.  FIXME: this should go away once GEP is the only
  97   // MAI
  98   //
  99   if (MAI.getNumIndices() == 0) {
 100     ++BBI;
 101     return false;
 102   }
 103
 104   BasicBlock *BB = MAI.getParent();
 105   Value *LastPtr = MAI.getPointerOperand();
 106
 107   // Remove the instruction from the stream
 108   BB->getInstList().remove(BBI);
 109
 110   // The vector of new instructions to be created
 111   std::vector<Instruction*> NewInsts;
 112
 113   // Process each index except the last one.
 114   User::const_op_iterator OI = MAI.idx_begin(), OE = MAI.idx_end();
 115   for (; OI+1 != OE; ++OI) {
 116     std::vector<Value*> Indices;
 117
 118     // If this is the first index and is 0, skip it and move on!
 119     if (OI == MAI.idx_begin()) {
 120       if (IsZero(*OI)) continue;
 121     } else
 122       // Not the first index: include initial [0] to deref the last ptr
 123       Indices.push_back(Constant::getNullValue(Type::UIntTy));
 124
 125     Indices.push_back(*OI);
 126
 127     // New Instruction: nextPtr1 = GetElementPtr LastPtr, Indices
 128     LastPtr = new GetElementPtrInst(LastPtr, Indices, "ptr1");
 129     NewInsts.push_back(cast<Instruction>(LastPtr));
 130     ++NumAdded;
 131   }
 132
 133   // Now create a new instruction to replace the original one
 134   //
 135   const PointerType *PtrTy = cast<PointerType>(LastPtr->getType());
 136
 137   // Get the final index vector, including an initial [0] as before.
 138   std::vector<Value*> Indices;
 139   Indices.push_back(Constant::getNullValue(Type::UIntTy));
 140   Indices.push_back(*OI);
 141
 142   Instruction *NewI = 0;
 143   switch(MAI.getOpcode()) {
 144   case Instruction::Load:
 145     NewI = new LoadInst(LastPtr, Indices, MAI.getName());
 146     break;
 147   case Instruction::Store:
 148     NewI = new StoreInst(MAI.getOperand(0), LastPtr, Indices);
 149     break;
 150   case Instruction::GetElementPtr:
 151     NewI = new GetElementPtrInst(LastPtr, Indices, MAI.getName());
 152     break;
 153   default:
 154     assert(0 && "Unrecognized memory access instruction");
 155   }
 156   NewInsts.push_back(NewI);
 157
 158   // Replace all uses of the old instruction with the new
 159   MAI.replaceAllUsesWith(NewI);
 160
 161   // Now delete the old instruction...
 162   delete &MAI;
 163
 164   // Insert all of the new instructions...
 165   BB->getInstList().insert(BBI, NewInsts.begin(), NewInsts.end());
 166
 167   // Advance the iterator to the instruction following the one just inserted...
 168   BBI = NewInsts.back();
 169   ++BBI;
 170   return true;
 171 }