Eliminate cast instructions: use only GEPs in decomposed sequence.

Don't decompose if there are 2 indices with 0 as first index.
Compute Changed flag correctly in runOnBasicBlock().


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@3233 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 70 insertions, 81 deletions

diff --git a/lib/Transforms/Scalar/DecomposeMultiDimRefs.cpp b/lib/Transforms/Scalar/DecomposeMultiDimRefs.cpp
index f0a8074..6576404 100644
--- a/lib/Transforms/Scalar/DecomposeMultiDimRefs.cpp
+++ b/lib/Transforms/Scalar/DecomposeMultiDimRefs.cpp
@@ -10,6 +10,7 @@
 
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/DerivedTypes.h"
+#include "llvm/Constants.h"
 #include "llvm/Constant.h"
 #include "llvm/iMemory.h"
 #include "llvm/iOther.h"
@@ -24,14 +25,16 @@ namespace {
     virtual bool runOnBasicBlock(BasicBlock &BB);
 
   private:
-    static void decomposeArrayRef(BasicBlock::iterator &BBI);
+    static bool decomposeArrayRef(BasicBlock::iterator &BBI);
   };
 
   RegisterOpt<DecomposePass> X("lowerrefs", "Decompose multi-dimensional "
                                "structure/array references");
 }
 
-Pass *createDecomposeMultiDimRefsPass() {
+Pass
+*createDecomposeMultiDimRefsPass()
+{
   return new DecomposePass();
 }
 
@@ -39,113 +42,99 @@ Pass *createDecomposeMultiDimRefsPass() {
 // runOnBasicBlock - Entry point for array or structure references with multiple
 // indices.
 //
-bool DecomposePass::runOnBasicBlock(BasicBlock &BB) {
+bool
+DecomposePass::runOnBasicBlock(BasicBlock &BB)
+{
   bool Changed = false;
   for (BasicBlock::iterator II = BB.begin(); II != BB.end(); ) {
-    if (MemAccessInst *MAI = dyn_cast<MemAccessInst>(&*II)) {
-      if (MAI->getNumOperands() > MAI->getFirstIndexOperandNumber()+1) {
-        decomposeArrayRef(II);
-        Changed = true;
-      } else {
-        ++II;
+    if (MemAccessInst *MAI = dyn_cast<MemAccessInst>(&*II))
+      if (MAI->getNumIndices() >= 2) {
+        Changed = decomposeArrayRef(II) || Changed; // always modifies II
+        continue;
       }
-    } else {
-      ++II;
-    }
+    ++II;
   }
-  
   return Changed;
 }
 
+// Check for a constant (uint) 0.
+inline bool
+IsZero(Value* idx)
+{
+  return (isa<ConstantInt>(idx) && cast<ConstantInt>(idx)->isNullValue());
+}
+
+// For any MemAccessInst with 2 or more array and structure indices:
 // 
-// For any combination of 2 or more array and structure indices,
-// this function repeats the foll. until we have a one-dim. reference: {
-//      ptr1 = getElementPtr [CompositeType-N] * lastPtr, uint firstIndex
-//      ptr2 = cast [CompositeType-N] * ptr1 to [CompositeType-N] *
-// }
-// Then it replaces the original instruction with an equivalent one that
-// uses the last ptr2 generated in the loop and a single index.
-// If any index is (uint) 0, we omit the getElementPtr instruction.
+//      opCode CompositeType* P, [uint|ubyte] idx1, ..., [uint|ubyte] idxN
 // 
-
-void DecomposePass::decomposeArrayRef(BasicBlock::iterator &BBI) {
+// this function generates the foll sequence:
+// 
+//      ptr1   = getElementPtr P,         idx1
+//      ptr2   = getElementPtr ptr1,   0, idx2
+//      ...
+//      ptrN-1 = getElementPtr ptrN-2, 0, idxN-1
+//      opCode                 ptrN-1, 0, idxN  // New-MAI
+// 
+// Then it replaces the original instruction with this sequence,
+// and replaces all uses of the original instruction with New-MAI.
+// If idx1 is 0, we simply omit the first getElementPtr instruction.
+// 
+// On return: BBI points to the instruction after the current one
+//            (whether or not *BBI was replaced).
+// 
+// Return value: true if the instruction was replaced; false otherwise.
+// 
+bool
+DecomposePass::decomposeArrayRef(BasicBlock::iterator &BBI)
+{
   MemAccessInst &MAI = cast<MemAccessInst>(*BBI);
+
+  // If this instr two or fewer arguments and the first argument is 0,
+  // the decomposed version is identical to the instruction itself.
+  // This is common enough that it is worth checking for explicitly...
+  if (MAI.getNumIndices() == 0 ||
+      (MAI.getNumIndices() <= 2 && IsZero(*MAI.idx_begin()))) {
+    ++BBI;
+    return false;
+  }
+
   BasicBlock *BB = MAI.getParent();
   Value *LastPtr = MAI.getPointerOperand();
 
   // Remove the instruction from the stream
   BB->getInstList().remove(BBI);
 
+  // The vector of new instructions to be created
   std::vector<Instruction*> NewInsts;
-  
-  // Process each index except the last one.
-  // 
 
+  // Process each index except the last one.
   User::const_op_iterator OI = MAI.idx_begin(), OE = MAI.idx_end();
   for (; OI+1 != OE; ++OI) {
-    assert(isa<PointerType>(LastPtr->getType()));
-      
-    // Check for a zero index.  This will need a cast instead of
-    // a getElementPtr, or it may need neither.
-    bool indexIsZero = isa<Constant>(*OI) && 
-                       cast<Constant>(OI->get())->isNullValue() &&
-                       OI->get()->getType() == Type::UIntTy;
-      
-    // Extract the first index.  If the ptr is a pointer to a structure
-    // and the next index is a structure offset (i.e., not an array offset), 
-    // we need to include an initial [0] to index into the pointer.
-    //
-
     std::vector<Value*> Indices;
-    const PointerType *PtrTy = cast<PointerType>(LastPtr->getType());
-
-    if (isa<StructType>(PtrTy->getElementType())
-        && !PtrTy->indexValid(*OI))
+    
+    // If this is the first index and is 0, skip it and move on!
+    if (OI == MAI.idx_begin()) {
+      if (IsZero(*OI)) continue;
+    } else
+      // Not the first index: include initial [0] to deref the last ptr
       Indices.push_back(Constant::getNullValue(Type::UIntTy));
+
     Indices.push_back(*OI);
 
-    // Get the type obtained by applying the first index.
-    // It must be a structure or array.
-    const Type *NextTy = MemAccessInst::getIndexedType(LastPtr->getType(),
-                                                       Indices, true);
-    assert(isa<CompositeType>(NextTy));
-    
-    // Get a pointer to the structure or to the elements of the array.
-    const Type *NextPtrTy =
-      PointerType::get(isa<StructType>(NextTy) ? NextTy
-                       : cast<ArrayType>(NextTy)->getElementType());
-      
-    // Instruction 1: nextPtr1 = GetElementPtr LastPtr, Indices
-    // This is not needed if the index is zero.
-    if (!indexIsZero) {
-      LastPtr = new GetElementPtrInst(LastPtr, Indices, "ptr1");
-      NewInsts.push_back(cast<Instruction>(LastPtr));
-      ++NumAdded;
-    }
-
-      
-    // Instruction 2: nextPtr2 = cast nextPtr1 to NextPtrTy
-    // This is not needed if the two types are identical.
-    //
-    if (LastPtr->getType() != NextPtrTy) {
-      LastPtr = new CastInst(LastPtr, NextPtrTy, "ptr2");
-      NewInsts.push_back(cast<Instruction>(LastPtr));
-      ++NumAdded;
-    }
+    // New Instruction: nextPtr1 = GetElementPtr LastPtr, Indices
+    LastPtr = new GetElementPtrInst(LastPtr, Indices, "ptr1");
+    NewInsts.push_back(cast<Instruction>(LastPtr));
+    ++NumAdded;
   }
-  
-  // 
+
   // Now create a new instruction to replace the original one
   //
   const PointerType *PtrTy = cast<PointerType>(LastPtr->getType());
 
-  // First, get the final index vector.  As above, we may need an initial [0].
-
+  // Get the final index vector, including an initial [0] as before.
   std::vector<Value*> Indices;
-  if (isa<StructType>(PtrTy->getElementType())
-      && !PtrTy->indexValid(*OI))
-    Indices.push_back(Constant::getNullValue(Type::UIntTy));
-
+  Indices.push_back(Constant::getNullValue(Type::UIntTy));
   Indices.push_back(*OI);
 
   Instruction *NewI = 0;
@@ -164,7 +153,6 @@ void DecomposePass::decomposeArrayRef(BasicBlock::iterator &BBI) {
   }
   NewInsts.push_back(NewI);
 
-  
   // Replace all uses of the old instruction with the new
   MAI.replaceAllUsesWith(NewI);
 
@@ -173,8 +161,9 @@ void DecomposePass::decomposeArrayRef(BasicBlock::iterator &BBI) {
 
   // Insert all of the new instructions...
   BB->getInstList().insert(BBI, NewInsts.begin(), NewInsts.end());
-  
+
   // Advance the iterator to the instruction following the one just inserted...
   BBI = NewInsts.back();
   ++BBI;
+  return true;
 }