Improve raising significantly

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

4 files changed, 267 insertions, 75 deletions

diff --git a/lib/Transforms/ExprTypeConvert.cpp b/lib/Transforms/ExprTypeConvert.cpp
index d8f6519..3b0f3d2 100644
--- a/lib/Transforms/ExprTypeConvert.cpp
+++ b/lib/Transforms/ExprTypeConvert.cpp
@@ -27,6 +27,33 @@ static inline const Type *getTy(const Value *V, ValueTypeCache &CT) {
   return I->second;
 }
 
+GetElementPtrInst *getAddToGEPResult(const Type *Ty, const Value *V) {
+  const StructType *StructTy = getPointedToStruct(Ty);
+  if (StructTy == 0) return 0;    // Must be a pointer to a struct...
+
+  // Must be a constant unsigned offset value... get it now...
+  if (!isa<ConstPoolUInt>(V)) return 0;
+  unsigned Offset = cast<ConstPoolUInt>(V)->getValue();
+ 
+  // Check to make sure the offset is somewhat legitiment w.r.t the struct
+  // type...
+  if (Offset >= TD.getTypeSize(StructTy)) return 0;
+  
+  // If we get this far, we have succeeded... TODO: We need to handle array
+  // indexing as well...
+  const StructLayout *SL = TD.getStructLayout(StructTy);
+  vector<ConstPoolVal*> Offsets;
+  unsigned ActualOffset = Offset;
+  const Type *ElTy = getStructOffsetType(StructTy, ActualOffset, Offsets);
+
+  if (ActualOffset != Offset) return 0;  // TODO: Handle Array indexing...
+ 
+  // Success!  Return the GEP instruction, with a dummy first argument.
+  ConstPoolVal *Dummy = ConstPoolVal::getNullConstant(Ty);
+  return new GetElementPtrInst(Dummy, Offsets);
+}
+
+
 
 static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
                                      ValueTypeCache &ConvertedTypes);
@@ -36,8 +63,8 @@ static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
 
 
 // ExpressionConvertableToType - Return true if it is possible
-static bool ExpressionConvertableToType(Value *V, const Type *Ty,
-                                        ValueTypeCache &CTMap) {
+bool ExpressionConvertableToType(Value *V, const Type *Ty,
+                                 ValueTypeCache &CTMap) {
   // Expression type must be holdable in a register.
   if (!isFirstClassType(Ty))
     return false;
@@ -58,12 +85,12 @@ static bool ExpressionConvertableToType(Value *V, const Type *Ty,
   if (I == 0) {
     // It's not an instruction, check to see if it's a constant... all constants
     // can be converted to an equivalent value (except pointers, they can't be
-    // const prop'd in general).
+    // const prop'd in general).  We just ask the constant propogator to see if
+    // it can convert the value...
     //
-    if (isa<ConstPoolVal>(V))
-      if (!isa<PointerType>(V->getType()) && !isa<PointerType>(Ty) &&
-          !isa<StructType>(Ty) && !isa<ArrayType>(Ty))
-        return true;
+    if (ConstPoolVal *CPV = dyn_cast<ConstPoolVal>(V))
+      if (opt::ConstantFoldCastInstruction(CPV, Ty))
+        return true;  // Don't worry about deallocating, it's a constant.
 
     return false;              // Otherwise, we can't convert!
   }
@@ -88,6 +115,7 @@ static bool ExpressionConvertableToType(Value *V, const Type *Ty,
   case Instruction::Load: {
     LoadInst *LI = cast<LoadInst>(I);
     if (LI->hasIndices()) return false;
+
     return ExpressionConvertableToType(LI->getPtrOperand(),
                                        PointerType::get(Ty), CTMap);
   }
@@ -137,8 +165,7 @@ static bool ExpressionConvertableToType(Value *V, const Type *Ty,
 
 
 
-static Value *ConvertExpressionToType(Value *V, const Type *Ty,
-                                      ValueMapCache &VMC) {
+Value *ConvertExpressionToType(Value *V, const Type *Ty, ValueMapCache &VMC) {
   ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(V);
   if (VMCI != VMC.ExprMap.end())
     return VMCI->second;
@@ -153,7 +180,6 @@ static Value *ConvertExpressionToType(Value *V, const Type *Ty,
       // Constants are converted by constant folding the cast that is required.
       // We assume here that all casts are implemented for constant prop.
       Value *Result = opt::ConstantFoldCastInstruction(CPV, Ty);
-      if (!Result) cerr << "Couldn't fold " << CPV << " to " << Ty << endl;
       assert(Result && "ConstantFoldCastInstruction Failed!!!");
 
       // Add the instruction to the expression map
@@ -334,8 +360,12 @@ bool RetValConvertableToType(Value *V, const Type *Ty,
 //
 static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
                                      ValueTypeCache &CTMap) {
-  assert(V->getType() != Ty &&
-         "OperandConvertableToType: Operand is already right type!");
+  if (V->getType() == Ty) return true;   // Already the right type?
+
+  // Expression type must be holdable in a register.
+  if (!isFirstClassType(Ty))
+    return false;
+
   Instruction *I = dyn_cast<Instruction>(U);
   if (I == 0) return false;              // We can't convert!
 
@@ -347,6 +377,17 @@ static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
     return losslessCastableTypes(Ty, I->getOperand(0)->getType());
 
   case Instruction::Add:
+    if (V == I->getOperand(0) && isa<CastInst>(I->getOperand(1))) {
+      Instruction *GEP =
+        getAddToGEPResult(Ty, cast<CastInst>(I->getOperand(1))->getOperand(0));
+      if (GEP) {  // If successful, this Add can be converted to a GEP.
+        const Type *RetTy = GEP->getType();  // Get the new type...
+        delete GEP;  // We don't want the actual instruction yet...
+        // Only successful if we can convert this type to the required type
+        return RetValConvertableToType(I, RetTy, CTMap);
+      }
+    }
+    // FALLTHROUGH
   case Instruction::Sub: {
     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
     return RetValConvertableToType(I, Ty, CTMap) &&
@@ -369,11 +410,32 @@ static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
     if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
       LoadInst *LI = cast<LoadInst>(I);
       const Type *PVTy = PT->getValueType();
-      if (LI->hasIndices() || isa<ArrayType>(PVTy) || 
-          TD.getTypeSize(PVTy) != TD.getTypeSize(LI->getType()))
+
+      if (LI->hasIndices() || isa<ArrayType>(PVTy))
+        return false;
+
+      if (!isFirstClassType(PVTy)) {
+        // They could be loading the first element of a structure type...
+        if (const StructType *ST = dyn_cast<StructType>(PVTy)) {
+          unsigned Offset = 0;   // No offset, get first leaf.
+          vector<ConstPoolVal*> Offsets;  // Discarded...
+          const Type *Ty = getStructOffsetType(ST, Offset, Offsets, false);
+          assert(Offset == 0 && "Offset changed from zero???");
+          if (!isFirstClassType(Ty)) return false;
+
+          // See if the leaf type is compatible with the old return type...
+          if (TD.getTypeSize(Ty) != TD.getTypeSize(LI->getType()))
+            return false;
+
+          return RetValConvertableToType(LI, Ty, CTMap);
+        }
+        return false;
+      }
+
+      if (TD.getTypeSize(PVTy) != TD.getTypeSize(LI->getType()))
         return false;
 
-      return RetValConvertableToType(LI, PT->getValueType(), CTMap);
+      return RetValConvertableToType(LI, PVTy, CTMap);
     }
     return false;
 
@@ -407,7 +469,7 @@ static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
     for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i)
       if (!ExpressionConvertableToType(PN->getIncomingValue(i), Ty, CTMap))
         return false;
-    return true;
+    return RetValConvertableToType(PN, Ty, CTMap);
   }
 
 #if 0
@@ -497,6 +559,17 @@ static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
     break;
 
   case Instruction::Add:
+    if (OldVal == I->getOperand(0) && isa<CastInst>(I->getOperand(1))) {
+      Res = getAddToGEPResult(NewVal->getType(),
+                              cast<CastInst>(I->getOperand(1))->getOperand(0));
+      if (Res) {  // If successful, this Add should be converted to a GEP.
+        // First operand is actually the given pointer...
+        Res->setOperand(0, NewVal);
+        break;
+      }
+    }
+    // FALLTHROUGH
+
   case Instruction::Sub:
   case Instruction::SetEQ:
   case Instruction::SetNE: {
@@ -519,11 +592,21 @@ static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
                         I->getOperand(1), Name);
     break;
 
-  case Instruction::Load:
-    assert(I->getOperand(0) == OldVal);
-    Res = new LoadInst(NewVal, Name);
+  case Instruction::Load: {
+    assert(I->getOperand(0) == OldVal && isa<PointerType>(NewVal->getType()));
+    const Type *PVTy = cast<PointerType>(NewVal->getType())->getValueType();
+    if (!isFirstClassType(PVTy)) {  // Must be an indirect load then...
+      assert(isa<StructType>(PVTy));
+      unsigned Offset = 0;   // No offset, get first leaf.
+      vector<ConstPoolVal*> Offsets;  // Discarded...
+      const Type *Ty = getStructOffsetType(PVTy, Offset, Offsets, false);
+      Res = new LoadInst(NewVal, Offsets, Name);
+    } else {
+      Res = new LoadInst(NewVal, Name);
+    }
+    assert(isFirstClassType(Res->getType()) && "Load of structure or array!");
     break;
-
+  }
   case Instruction::Store: {
     if (I->getOperand(0) == OldVal) {  // Replace the source value
       const PointerType *NewPT = PointerType::get(NewTy);
@@ -678,7 +761,7 @@ ValueHandle::~ValueHandle() {
     // loops.  Note that we cannot use DCE because DCE won't remove a store
     // instruction, for example.
     //
-    RecursiveDelete(cast<Instruction>(V));
+    RecursiveDelete(dyn_cast<Instruction>(V));
   } else {
 #ifdef DEBUG_EXPR_CONVERT
     cerr << "VH RELEASING: " << (void*)Operands[0].get() << " " << Operands[0]->use_size() << " " << Operands[0];
diff --git a/lib/Transforms/LevelRaise.cpp b/lib/Transforms/LevelRaise.cpp
index 13140b4..310c797 100644
--- a/lib/Transforms/LevelRaise.cpp
+++ b/lib/Transforms/LevelRaise.cpp
@@ -68,53 +68,6 @@ static inline bool isReinterpretingCast(const CastInst *CI) {
 }
 
 
-// getPointedToStruct - If the argument is a pointer type, and the pointed to
-// value is a struct type, return the struct type, else return null.
-//
-static const StructType *getPointedToStruct(const Type *Ty) {
-  const PointerType *PT = dyn_cast<PointerType>(Ty);
-  return PT ? dyn_cast<StructType>(PT->getValueType()) : 0;
-}
-
-
-// getStructOffsetType - Return a vector of offsets that are to be used to index
-// into the specified struct type to get as close as possible to index as we
-// can.  Note that it is possible that we cannot get exactly to Offset, in which
-// case we update offset to be the offset we actually obtained.  The resultant
-// leaf type is returned.
-//
-static const Type *getStructOffsetType(const Type *Ty, unsigned &Offset,
-                                       vector<ConstPoolVal*> &Offsets) {
-  if (!isa<StructType>(Ty)) {
-    Offset = 0;   // Return the offset that we were able to acheive
-    return Ty;    // Return the leaf type
-  }
-
-  assert(Offset < TD.getTypeSize(Ty) && "Offset not in struct!");
-  const StructType *STy = cast<StructType>(Ty);
-  const StructLayout *SL = TD.getStructLayout(STy);
-
-  // This loop terminates always on a 0 <= i < MemberOffsets.size()
-  unsigned i;
-  for (i = 0; i < SL->MemberOffsets.size()-1; ++i)
-    if (Offset >= SL->MemberOffsets[i] && Offset <  SL->MemberOffsets[i+1])
-      break;
-  
-  assert(Offset >= SL->MemberOffsets[i] &&
-         (i == SL->MemberOffsets.size()-1 || Offset <  SL->MemberOffsets[i+1]));
-
-  // Make sure to save the current index...
-  Offsets.push_back(ConstPoolUInt::get(Type::UByteTy, i));
-
-  unsigned SubOffs = Offset - SL->MemberOffsets[i];
-  const Type *LeafTy = getStructOffsetType(STy->getElementTypes()[i], SubOffs,
-                                           Offsets);
-  Offset = SL->MemberOffsets[i] + SubOffs;
-  return LeafTy;
-}
-
-
-
 
 
 // DoInsertArrayCast - If the argument value has a pointer type, and if the
@@ -375,15 +328,40 @@ static bool PeepholeOptimize(BasicBlock *BB, BasicBlock::iterator &BI) {
       if (RetValConvertableToType(CI, Src->getType(), ConvertedTypes)) {
         PRINT_PEEPHOLE2("CAST-DEST-EXPR-CONV:in ", CI, Src);
 
-        //cerr << "\nCONVERTING EXPR TYPE:\n";
+#ifdef DEBUG_PEEPHOLE_INSTS
+        cerr << "\nCONVERTING EXPR TYPE:\n";
+#endif
         ValueMapCache ValueMap;
         ConvertUsersType(CI, Src, ValueMap);  // This will delete CI!
 
         BI = BB->begin();  // Rescan basic block.  BI might be invalidated.
         PRINT_PEEPHOLE1("CAST-DEST-EXPR-CONV:out", Src);
-        //cerr << "DONE CONVERTING EXPR TYPE: ";// << BB->getParent();
+#ifdef DEBUG_PEEPHOLE_INSTS
+        cerr << "DONE CONVERTING EXPR TYPE: \n\n";// << BB->getParent();
+#endif
         return true;
+      } else {
+        ConvertedTypes.clear();
+        if (ExpressionConvertableToType(Src, DestTy, ConvertedTypes)) {
+          PRINT_PEEPHOLE2("CAST-SRC-EXPR-CONV:in ", CI, Src);
+          
+#ifdef DEBUG_PEEPHOLE_INSTS
+          cerr << "\nCONVERTING SRC EXPR TYPE:\n";
+#endif
+          ValueMapCache ValueMap;
+          Value *E = ConvertExpressionToType(Src, DestTy, ValueMap);
+          if (ConstPoolVal *CPV = dyn_cast<ConstPoolVal>(E))
+            CI->replaceAllUsesWith(CPV);
+
+          BI = BB->begin();  // Rescan basic block.  BI might be invalidated.
+          PRINT_PEEPHOLE1("CAST-SRC-EXPR-CONV:out", E);
+#ifdef DEBUG_PEEPHOLE_INSTS
+          cerr << "DONE CONVERTING SRC EXPR TYPE: \n\n";// << BB->getParent();
+#endif
+          return true;
+        }
       }
+      
     }
 
     // Check to see if we are casting from a structure pointer to a pointer to
@@ -396,6 +374,7 @@ static bool PeepholeOptimize(BasicBlock *BB, BasicBlock::iterator &BI) {
     // Into: %t2 = getelementptr {<...>} * %StructPtr, <0, 0, 0, ...>
     //       %t1 = cast <eltype> * %t1 to <ty> *
     //
+#if 1
     if (const StructType *STy = getPointedToStruct(Src->getType()))
       if (const PointerType *DestPTy = dyn_cast<PointerType>(DestTy)) {
 
@@ -463,7 +442,7 @@ static bool PeepholeOptimize(BasicBlock *BB, BasicBlock::iterator &BI) {
           }
         }
       }
-
+#endif
 
   } else if (MallocInst *MI = dyn_cast<MallocInst>(I)) {
     if (PeepholeMallocInst(BB, BI)) return true;
@@ -482,10 +461,17 @@ static bool PeepholeOptimize(BasicBlock *BB, BasicBlock::iterator &BI) {
     // Into: store <elementty> %v, {<...>} * %StructPtr, <element indices>
     //
     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Pointer)) {
+      // Append any indices that the store instruction has onto the end of the
+      // ones that the GEP is carrying...
+      //
+      vector<ConstPoolVal*> Indices(GEP->getIndices());
+      Indices.insert(Indices.end(), SI->getIndices().begin(),
+                     SI->getIndices().end());
+
       PRINT_PEEPHOLE2("gep-store:in", GEP, SI);
       ReplaceInstWithInst(BB->getInstList(), BI,
                           SI = new StoreInst(Val, GEP->getPtrOperand(),
-                                             GEP->getIndices()));
+                                             Indices));
       PRINT_PEEPHOLE1("gep-store:out", SI);
       return true;
     }
@@ -530,13 +516,59 @@ static bool PeepholeOptimize(BasicBlock *BB, BasicBlock::iterator &BI) {
     // Into: load {<...>} * %StructPtr, <element indices>
     //
     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Pointer)) {
+      // Append any indices that the load instruction has onto the end of the
+      // ones that the GEP is carrying...
+      //
+      vector<ConstPoolVal*> Indices(GEP->getIndices());
+      Indices.insert(Indices.end(), LI->getIndices().begin(),
+                     LI->getIndices().end());
+
       PRINT_PEEPHOLE2("gep-load:in", GEP, LI);
       ReplaceInstWithInst(BB->getInstList(), BI,
                           LI = new LoadInst(GEP->getPtrOperand(),
-                                            GEP->getIndices()));
+                                            Indices));
       PRINT_PEEPHOLE1("gep-load:out", LI);
       return true;
     }
+
+
+    // Peephole optimize the following instructions:
+    // %t1 = cast <ty> * %t0 to <ty2> *
+    // %V  = load <ty2> * %t1
+    //
+    // Into: %t1 = load <ty> * %t0
+    //       %V  = cast <ty> %t1 to <ty2>
+    //
+    // The idea behind this transformation is that if the expression type
+    // conversion engine could not convert the cast into some other nice form,
+    // that there is something fundementally wrong with the current shape of
+    // the program.  Move the cast through the load and try again.  This will
+    // leave the original cast instruction, to presumably become dead.
+    //
+    if (CastInst *CI = dyn_cast<CastInst>(Pointer)) {
+      Value *SrcVal = CI->getOperand(0);
+      const PointerType *SrcTy = dyn_cast<PointerType>(SrcVal->getType());
+      const Type *ElTy = SrcTy ? SrcTy->getValueType() : 0;
+
+      // Make sure that nothing will be lost in the new cast...
+      if (SrcTy && losslessCastableTypes(ElTy, LI->getType())) {
+        PRINT_PEEPHOLE2("CL-LoadCast:in ", CI, LI);
+
+        string CName = CI->getName(); CI->setName("");
+        LoadInst *NLI = new LoadInst(SrcVal, LI->getName());
+        LI->setName("");  // Take over the old load's name
+
+        // Insert the load before the old load
+        BI = BB->getInstList().insert(BI, NLI)+1;
+
+        // Replace the old load with a new cast...
+        ReplaceInstWithInst(BB->getInstList(), BI, 
+                            CI = new CastInst(NLI, LI->getType(), CName));
+        PRINT_PEEPHOLE2("CL-LoadCast:out", NLI, CI);
+
+        return true;
+      }
+    }
   } else if (I->getOpcode() == Instruction::Add &&
              isa<CastInst>(I->getOperand(1))) {
 
@@ -580,6 +612,7 @@ static bool PeepholeOptimize(BasicBlock *BB, BasicBlock::iterator &BI) {
       }
 
       GetElementPtrInst *GEP = new GetElementPtrInst(SrcPtr, Offsets);
+      //AddOp2->getName());
       BI = BB->getInstList().insert(BI, GEP)+1;
 
       assert(Offset-ActualOffset == 0  &&
@@ -605,8 +638,12 @@ static bool DoRaisePass(Method *M) {
     BasicBlock::InstListType &BIL = BB->getInstList();
 
     for (BasicBlock::iterator BI = BB->begin(); BI != BB->end();) {
-      if (opt::DeadCodeElimination::dceInstruction(BIL, BI) ||
-          PeepholeOptimize(BB, BI))
+      if (opt::DeadCodeElimination::dceInstruction(BIL, BI)) {
+        Changed = true; 
+#ifdef DEBUG_PEEPHOLE_INSTS
+        cerr << "DeadCode Elinated!\n";
+#endif
+      } else if (PeepholeOptimize(BB, BI))
         Changed = true;
       else
         ++BI;
@@ -629,6 +666,7 @@ bool RaisePointerReferences::doit(Method *M) {
 
   while (DoRaisePass(M)) Changed = true;
 
+#if 0
   // PtrCasts - Keep a mapping between the pointer values (the key of the 
   // map), and the cast to array pointer (the value) in this map.  This is
   // used when converting pointer math into array addressing.
@@ -645,6 +683,7 @@ bool RaisePointerReferences::doit(Method *M) {
   //
   Changed |= reduce_apply_bool(PtrCasts.begin(), PtrCasts.end(), 
                                ptr_fun(DoEliminatePointerArithmetic));
+#endif
 
   return Changed;
 }
diff --git a/lib/Transforms/TransformInternals.cpp b/lib/Transforms/TransformInternals.cpp
index e7eef2d..ac8181b 100644
--- a/lib/Transforms/TransformInternals.cpp
+++ b/lib/Transforms/TransformInternals.cpp
@@ -8,6 +8,7 @@
 #include "TransformInternals.h"
 #include "llvm/Method.h"
 #include "llvm/Type.h"
+#include "llvm/ConstPoolVals.h"
 
 // TargetData Hack: Eventually we will have annotations given to us by the
 // backend so that we know stuff about type size and alignments.  For now
@@ -87,3 +88,44 @@ void ReplaceInstWithInst(BasicBlock::InstListType &BIL,
 }
 
 
+// getStructOffsetType - Return a vector of offsets that are to be used to index
+// into the specified struct type to get as close as possible to index as we
+// can.  Note that it is possible that we cannot get exactly to Offset, in which
+// case we update offset to be the offset we actually obtained.  The resultant
+// leaf type is returned.
+//
+// If StopEarly is set to true (the default), the first object with the
+// specified type is returned, even if it is a struct type itself.  In this
+// case, this routine will not drill down to the leaf type.  Set StopEarly to
+// false if you want a leaf
+//
+const Type *getStructOffsetType(const Type *Ty, unsigned &Offset,
+                                vector<ConstPoolVal*> &Offsets,
+                                bool StopEarly = true) {
+  if (!isa<StructType>(Ty) || (Offset == 0 && StopEarly)) {
+    Offset = 0;   // Return the offset that we were able to acheive
+    return Ty;    // Return the leaf type
+  }
+
+  assert(Offset < TD.getTypeSize(Ty) && "Offset not in struct!");
+  const StructType *STy = cast<StructType>(Ty);
+  const StructLayout *SL = TD.getStructLayout(STy);
+
+  // This loop terminates always on a 0 <= i < MemberOffsets.size()
+  unsigned i;
+  for (i = 0; i < SL->MemberOffsets.size()-1; ++i)
+    if (Offset >= SL->MemberOffsets[i] && Offset <  SL->MemberOffsets[i+1])
+      break;
+  
+  assert(Offset >= SL->MemberOffsets[i] &&
+         (i == SL->MemberOffsets.size()-1 || Offset <  SL->MemberOffsets[i+1]));
+
+  // Make sure to save the current index...
+  Offsets.push_back(ConstPoolUInt::get(Type::UByteTy, i));
+
+  unsigned SubOffs = Offset - SL->MemberOffsets[i];
+  const Type *LeafTy = getStructOffsetType(STy->getElementTypes()[i], SubOffs,
+                                           Offsets);
+  Offset = SL->MemberOffsets[i] + SubOffs;
+  return LeafTy;
+}
diff --git a/lib/Transforms/TransformInternals.h b/lib/Transforms/TransformInternals.h
index 94af200..ea42732 100644
--- a/lib/Transforms/TransformInternals.h
+++ b/lib/Transforms/TransformInternals.h
@@ -11,6 +11,7 @@
 #include "llvm/BasicBlock.h"
 #include "llvm/Instruction.h"
 #include "llvm/Target/TargetData.h"
+#include "llvm/DerivedTypes.h"
 #include <map>
 #include <set>
 
@@ -36,6 +37,14 @@ static inline bool isFirstClassType(const Type *Ty) {
   return Ty->isPrimitiveType() || Ty->isPointerType();
 }
 
+// getPointedToStruct - If the argument is a pointer type, and the pointed to
+// value is a struct type, return the struct type, else return null.
+//
+static inline const StructType *getPointedToStruct(const Type *Ty) {
+  const PointerType *PT = dyn_cast<PointerType>(Ty);
+  return PT ? dyn_cast<StructType>(PT->getValueType()) : 0;
+}
+
 
 // ReplaceInstWithValue - Replace all uses of an instruction (specified by BI)
 // with a value, then remove and delete the original instruction.
@@ -68,6 +77,10 @@ struct ValueMapCache {
   typedef map<const Value *, Value *> ExprMapTy;
 };
 
+
+bool ExpressionConvertableToType(Value *V, const Type *Ty, ValueTypeCache &Map);
+Value *ConvertExpressionToType(Value *V, const Type *Ty, ValueMapCache &VMC);
+
 // RetValConvertableToType - Return true if it is possible
 bool RetValConvertableToType(Value *V, const Type *Ty,
                              ValueTypeCache &ConvertedTypes);
@@ -102,4 +115,19 @@ public:
   }
 };
 
+// getStructOffsetType - Return a vector of offsets that are to be used to index
+// into the specified struct type to get as close as possible to index as we
+// can.  Note that it is possible that we cannot get exactly to Offset, in which
+// case we update offset to be the offset we actually obtained.  The resultant
+// leaf type is returned.
+//
+// If StopEarly is set to true (the default), the first object with the
+// specified type is returned, even if it is a struct type itself.  In this
+// case, this routine will not drill down to the leaf type.  Set StopEarly to
+// false if you want a leaf
+//
+const Type *getStructOffsetType(const Type *Ty, unsigned &Offset,
+                                vector<ConstPoolVal*> &Offsets,
+                                bool StopEarly = true);
+
 #endif