LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

ExprTypeConvert.cpp

Go to the documentation of this file.
00001 //===- ExprTypeConvert.cpp - Code to change an LLVM Expr Type -------------===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the part of level raising that checks to see if it is
00011 // possible to coerce an entire expression tree into a different type.  If
00012 // convertible, other routines from this file will do the conversion.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "TransformInternals.h"
00017 #include "llvm/Constants.h"
00018 #include "llvm/Instructions.h"
00019 #include "llvm/Analysis/Expressions.h"
00020 #include "llvm/ADT/STLExtras.h"
00021 #include "llvm/Support/Debug.h"
00022 #include <algorithm>
00023 using namespace llvm;
00024 
00025 static bool OperandConvertibleToType(User *U, Value *V, const Type *Ty,
00026                                      ValueTypeCache &ConvertedTypes,
00027                                      const TargetData &TD);
00028 
00029 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
00030                                  ValueMapCache &VMC, const TargetData &TD);
00031 
00032 // Peephole Malloc instructions: we take a look at the use chain of the
00033 // malloc instruction, and try to find out if the following conditions hold:
00034 //   1. The malloc is of the form: 'malloc [sbyte], uint <constant>'
00035 //   2. The only users of the malloc are cast & add instructions
00036 //   3. Of the cast instructions, there is only one destination pointer type
00037 //      [RTy] where the size of the pointed to object is equal to the number
00038 //      of bytes allocated.
00039 //
00040 // If these conditions hold, we convert the malloc to allocate an [RTy]
00041 // element.  TODO: This comment is out of date WRT arrays
00042 //
00043 static bool MallocConvertibleToType(MallocInst *MI, const Type *Ty,
00044                                     ValueTypeCache &CTMap,
00045                                     const TargetData &TD) {
00046   if (!isa<PointerType>(Ty)) return false;   // Malloc always returns pointers
00047 
00048   // Deal with the type to allocate, not the pointer type...
00049   Ty = cast<PointerType>(Ty)->getElementType();
00050   if (!Ty->isSized()) return false;      // Can only alloc something with a size
00051 
00052   // Analyze the number of bytes allocated...
00053   ExprType Expr = ClassifyExpr(MI->getArraySize());
00054 
00055   // Get information about the base datatype being allocated, before & after
00056   int ReqTypeSize = TD.getTypeSize(Ty);
00057   if (ReqTypeSize == 0) return false;
00058   unsigned OldTypeSize = TD.getTypeSize(MI->getType()->getElementType());
00059 
00060   // Must have a scale or offset to analyze it...
00061   if (!Expr.Offset && !Expr.Scale && OldTypeSize == 1) return false;
00062 
00063   // Get the offset and scale of the allocation...
00064   int64_t OffsetVal = Expr.Offset ? getConstantValue(Expr.Offset) : 0;
00065   int64_t ScaleVal = Expr.Scale ? getConstantValue(Expr.Scale) :(Expr.Var != 0);
00066 
00067   // The old type might not be of unit size, take old size into consideration
00068   // here...
00069   int64_t Offset = OffsetVal * OldTypeSize;
00070   int64_t Scale  = ScaleVal  * OldTypeSize;
00071   
00072   // In order to be successful, both the scale and the offset must be a multiple
00073   // of the requested data type's size.
00074   //
00075   if (Offset/ReqTypeSize*ReqTypeSize != Offset ||
00076       Scale/ReqTypeSize*ReqTypeSize != Scale)
00077     return false;   // Nope.
00078 
00079   return true;
00080 }
00081 
00082 static Instruction *ConvertMallocToType(MallocInst *MI, const Type *Ty,
00083                                         const std::string &Name,
00084                                         ValueMapCache &VMC,
00085                                         const TargetData &TD){
00086   BasicBlock *BB = MI->getParent();
00087   BasicBlock::iterator It = BB->end();
00088 
00089   // Analyze the number of bytes allocated...
00090   ExprType Expr = ClassifyExpr(MI->getArraySize());
00091 
00092   const PointerType *AllocTy = cast<PointerType>(Ty);
00093   const Type *ElType = AllocTy->getElementType();
00094 
00095   unsigned DataSize = TD.getTypeSize(ElType);
00096   unsigned OldTypeSize = TD.getTypeSize(MI->getType()->getElementType());
00097 
00098   // Get the offset and scale coefficients that we are allocating...
00099   int64_t OffsetVal = (Expr.Offset ? getConstantValue(Expr.Offset) : 0);
00100   int64_t ScaleVal = Expr.Scale ? getConstantValue(Expr.Scale) : (Expr.Var !=0);
00101 
00102   // The old type might not be of unit size, take old size into consideration
00103   // here...
00104   unsigned Offset = (uint64_t)OffsetVal * OldTypeSize / DataSize;
00105   unsigned Scale  = (uint64_t)ScaleVal  * OldTypeSize / DataSize;
00106 
00107   // Locate the malloc instruction, because we may be inserting instructions
00108   It = MI;
00109 
00110   // If we have a scale, apply it first...
00111   if (Expr.Var) {
00112     // Expr.Var is not necessarily unsigned right now, insert a cast now.
00113     if (Expr.Var->getType() != Type::UIntTy)
00114       Expr.Var = new CastInst(Expr.Var, Type::UIntTy,
00115                               Expr.Var->getName()+"-uint", It);
00116 
00117     if (Scale != 1)
00118       Expr.Var = BinaryOperator::create(Instruction::Mul, Expr.Var,
00119                                         ConstantUInt::get(Type::UIntTy, Scale),
00120                                         Expr.Var->getName()+"-scl", It);
00121 
00122   } else {
00123     // If we are not scaling anything, just make the offset be the "var"...
00124     Expr.Var = ConstantUInt::get(Type::UIntTy, Offset);
00125     Offset = 0; Scale = 1;
00126   }
00127 
00128   // If we have an offset now, add it in...
00129   if (Offset != 0) {
00130     assert(Expr.Var && "Var must be nonnull by now!");
00131     Expr.Var = BinaryOperator::create(Instruction::Add, Expr.Var,
00132                                       ConstantUInt::get(Type::UIntTy, Offset),
00133                                       Expr.Var->getName()+"-off", It);
00134   }
00135 
00136   assert(AllocTy == Ty);
00137   return new MallocInst(AllocTy->getElementType(), Expr.Var, Name);
00138 }
00139 
00140 
00141 // ExpressionConvertibleToType - Return true if it is possible
00142 bool llvm::ExpressionConvertibleToType(Value *V, const Type *Ty,
00143                                  ValueTypeCache &CTMap, const TargetData &TD) {
00144   // Expression type must be holdable in a register.
00145   if (!Ty->isFirstClassType())
00146     return false;
00147   
00148   ValueTypeCache::iterator CTMI = CTMap.find(V);
00149   if (CTMI != CTMap.end()) return CTMI->second == Ty;
00150 
00151   // If it's a constant... all constants can be converted to a different
00152   // type.
00153   //
00154   if (isa<Constant>(V) && !isa<GlobalValue>(V))
00155     return true;
00156   
00157   CTMap[V] = Ty;
00158   if (V->getType() == Ty) return true;  // Expression already correct type!
00159 
00160   Instruction *I = dyn_cast<Instruction>(V);
00161   if (I == 0) return false;              // Otherwise, we can't convert!
00162 
00163   switch (I->getOpcode()) {
00164   case Instruction::Cast:
00165     // We can convert the expr if the cast destination type is losslessly
00166     // convertible to the requested type.
00167     if (!Ty->isLosslesslyConvertibleTo(I->getType())) return false;
00168 
00169     // We also do not allow conversion of a cast that casts from a ptr to array
00170     // of X to a *X.  For example: cast [4 x %List *] * %val to %List * *
00171     //
00172     if (const PointerType *SPT = 
00173         dyn_cast<PointerType>(I->getOperand(0)->getType()))
00174       if (const PointerType *DPT = dyn_cast<PointerType>(I->getType()))
00175         if (const ArrayType *AT = dyn_cast<ArrayType>(SPT->getElementType()))
00176           if (AT->getElementType() == DPT->getElementType())
00177             return false;
00178     break;
00179 
00180   case Instruction::Add:
00181   case Instruction::Sub:
00182     if (!Ty->isInteger() && !Ty->isFloatingPoint()) return false;
00183     if (!ExpressionConvertibleToType(I->getOperand(0), Ty, CTMap, TD) ||
00184         !ExpressionConvertibleToType(I->getOperand(1), Ty, CTMap, TD))
00185       return false;
00186     break;
00187   case Instruction::Shr:
00188     if (!Ty->isInteger()) return false;
00189     if (Ty->isSigned() != V->getType()->isSigned()) return false;
00190     // FALL THROUGH
00191   case Instruction::Shl:
00192     if (!Ty->isInteger()) return false;
00193     if (!ExpressionConvertibleToType(I->getOperand(0), Ty, CTMap, TD))
00194       return false;
00195     break;
00196 
00197   case Instruction::Load: {
00198     LoadInst *LI = cast<LoadInst>(I);
00199     if (!ExpressionConvertibleToType(LI->getPointerOperand(),
00200                                      PointerType::get(Ty), CTMap, TD))
00201       return false;
00202     break;                                     
00203   }
00204   case Instruction::PHI: {
00205     PHINode *PN = cast<PHINode>(I);
00206     // Be conservative if we find a giant PHI node.
00207     if (PN->getNumIncomingValues() > 32) return false;
00208 
00209     for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i)
00210       if (!ExpressionConvertibleToType(PN->getIncomingValue(i), Ty, CTMap, TD))
00211         return false;
00212     break;
00213   }
00214 
00215   case Instruction::Malloc:
00216     if (!MallocConvertibleToType(cast<MallocInst>(I), Ty, CTMap, TD))
00217       return false;
00218     break;
00219 
00220   case Instruction::GetElementPtr: {
00221     // GetElementPtr's are directly convertible to a pointer type if they have
00222     // a number of zeros at the end.  Because removing these values does not
00223     // change the logical offset of the GEP, it is okay and fair to remove them.
00224     // This can change this:
00225     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
00226     //   %t2 = cast %List * * %t1 to %List *
00227     // into
00228     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
00229     // 
00230     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
00231     const PointerType *PTy = dyn_cast<PointerType>(Ty);
00232     if (!PTy) return false;  // GEP must always return a pointer...
00233     const Type *PVTy = PTy->getElementType();
00234 
00235     // Check to see if there are zero elements that we can remove from the
00236     // index array.  If there are, check to see if removing them causes us to
00237     // get to the right type...
00238     //
00239     std::vector<Value*> Indices(GEP->idx_begin(), GEP->idx_end());
00240     const Type *BaseType = GEP->getPointerOperand()->getType();
00241     const Type *ElTy = 0;
00242 
00243     while (!Indices.empty() &&
00244            Indices.back() == Constant::getNullValue(Indices.back()->getType())){
00245       Indices.pop_back();
00246       ElTy = GetElementPtrInst::getIndexedType(BaseType, Indices, true);
00247       if (ElTy == PVTy)
00248         break;  // Found a match!!
00249       ElTy = 0;
00250     }
00251 
00252     if (ElTy) break;   // Found a number of zeros we can strip off!
00253 
00254     // Otherwise, we can convert a GEP from one form to the other iff the
00255     // current gep is of the form 'getelementptr sbyte*, long N
00256     // and we could convert this to an appropriate GEP for the new type.
00257     //
00258     if (GEP->getNumOperands() == 2 &&
00259         GEP->getType() == PointerType::get(Type::SByteTy)) {
00260 
00261       // Do not Check to see if our incoming pointer can be converted
00262       // to be a ptr to an array of the right type... because in more cases than
00263       // not, it is simply not analyzable because of pointer/array
00264       // discrepancies.  To fix this, we will insert a cast before the GEP.
00265       //
00266 
00267       // Check to see if 'N' is an expression that can be converted to
00268       // the appropriate size... if so, allow it.
00269       //
00270       std::vector<Value*> Indices;
00271       const Type *ElTy = ConvertibleToGEP(PTy, I->getOperand(1), Indices, TD);
00272       if (ElTy == PVTy) {
00273         if (!ExpressionConvertibleToType(I->getOperand(0),
00274                                          PointerType::get(ElTy), CTMap, TD))
00275           return false;  // Can't continue, ExConToTy might have polluted set!
00276         break;
00277       }
00278     }
00279 
00280     // Otherwise, it could be that we have something like this:
00281     //     getelementptr [[sbyte] *] * %reg115, long %reg138    ; [sbyte]**
00282     // and want to convert it into something like this:
00283     //     getelemenptr [[int] *] * %reg115, long %reg138      ; [int]**
00284     //
00285     if (GEP->getNumOperands() == 2 && 
00286         PTy->getElementType()->isSized() &&
00287         TD.getTypeSize(PTy->getElementType()) == 
00288         TD.getTypeSize(GEP->getType()->getElementType())) {
00289       const PointerType *NewSrcTy = PointerType::get(PVTy);
00290       if (!ExpressionConvertibleToType(I->getOperand(0), NewSrcTy, CTMap, TD))
00291         return false;
00292       break;
00293     }
00294 
00295     return false;   // No match, maybe next time.
00296   }
00297 
00298   case Instruction::Call: {
00299     if (isa<Function>(I->getOperand(0)))
00300       return false;  // Don't even try to change direct calls.
00301 
00302     // If this is a function pointer, we can convert the return type if we can
00303     // convert the source function pointer.
00304     //
00305     const PointerType *PT = cast<PointerType>(I->getOperand(0)->getType());
00306     const FunctionType *FT = cast<FunctionType>(PT->getElementType());
00307     std::vector<const Type *> ArgTys(FT->param_begin(), FT->param_end());
00308     const FunctionType *NewTy =
00309       FunctionType::get(Ty, ArgTys, FT->isVarArg());
00310     if (!ExpressionConvertibleToType(I->getOperand(0),
00311                                      PointerType::get(NewTy), CTMap, TD))
00312       return false;
00313     break;
00314   }
00315   default:
00316     return false;
00317   }
00318 
00319   // Expressions are only convertible if all of the users of the expression can
00320   // have this value converted.  This makes use of the map to avoid infinite
00321   // recursion.
00322   //
00323   for (Value::use_iterator It = I->use_begin(), E = I->use_end(); It != E; ++It)
00324     if (!OperandConvertibleToType(*It, I, Ty, CTMap, TD))
00325       return false;
00326 
00327   return true;
00328 }
00329 
00330 
00331 Value *llvm::ConvertExpressionToType(Value *V, const Type *Ty, 
00332                                      ValueMapCache &VMC, const TargetData &TD) {
00333   if (V->getType() == Ty) return V;  // Already where we need to be?
00334 
00335   ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(V);
00336   if (VMCI != VMC.ExprMap.end()) {
00337     const Value *GV = VMCI->second;
00338     const Type *GTy = VMCI->second->getType();
00339     assert(VMCI->second->getType() == Ty);
00340 
00341     if (Instruction *I = dyn_cast<Instruction>(V))
00342       ValueHandle IHandle(VMC, I);  // Remove I if it is unused now!
00343 
00344     return VMCI->second;
00345   }
00346 
00347   DEBUG(std::cerr << "CETT: " << (void*)V << " " << *V);
00348 
00349   Instruction *I = dyn_cast<Instruction>(V);
00350   if (I == 0) {
00351     Constant *CPV = cast<Constant>(V);
00352     // Constants are converted by constant folding the cast that is required.
00353     // We assume here that all casts are implemented for constant prop.
00354     Value *Result = ConstantExpr::getCast(CPV, Ty);
00355     // Add the instruction to the expression map
00356     //VMC.ExprMap[V] = Result;
00357     return Result;
00358   }
00359 
00360 
00361   BasicBlock *BB = I->getParent();
00362   std::string Name = I->getName();  if (!Name.empty()) I->setName("");
00363   Instruction *Res;     // Result of conversion
00364 
00365   ValueHandle IHandle(VMC, I);  // Prevent I from being removed!
00366   
00367   Constant *Dummy = Constant::getNullValue(Ty);
00368 
00369   switch (I->getOpcode()) {
00370   case Instruction::Cast:
00371     assert(VMC.NewCasts.count(ValueHandle(VMC, I)) == 0);
00372     Res = new CastInst(I->getOperand(0), Ty, Name);
00373     VMC.NewCasts.insert(ValueHandle(VMC, Res));
00374     break;
00375     
00376   case Instruction::Add:
00377   case Instruction::Sub:
00378     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
00379                                  Dummy, Dummy, Name);
00380     VMC.ExprMap[I] = Res;   // Add node to expression eagerly
00381 
00382     Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC, TD));
00383     Res->setOperand(1, ConvertExpressionToType(I->getOperand(1), Ty, VMC, TD));
00384     break;
00385 
00386   case Instruction::Shl:
00387   case Instruction::Shr:
00388     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), Dummy,
00389                         I->getOperand(1), Name);
00390     VMC.ExprMap[I] = Res;
00391     Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC, TD));
00392     break;
00393 
00394   case Instruction::Load: {
00395     LoadInst *LI = cast<LoadInst>(I);
00396 
00397     Res = new LoadInst(Constant::getNullValue(PointerType::get(Ty)), Name);
00398     VMC.ExprMap[I] = Res;
00399     Res->setOperand(0, ConvertExpressionToType(LI->getPointerOperand(),
00400                                                PointerType::get(Ty), VMC, TD));
00401     assert(Res->getOperand(0)->getType() == PointerType::get(Ty));
00402     assert(Ty == Res->getType());
00403     assert(Res->getType()->isFirstClassType() && "Load of structure or array!");
00404     break;
00405   }
00406 
00407   case Instruction::PHI: {
00408     PHINode *OldPN = cast<PHINode>(I);
00409     PHINode *NewPN = new PHINode(Ty, Name);
00410 
00411     VMC.ExprMap[I] = NewPN;   // Add node to expression eagerly
00412     while (OldPN->getNumOperands()) {
00413       BasicBlock *BB = OldPN->getIncomingBlock(0);
00414       Value *OldVal = OldPN->getIncomingValue(0);
00415       ValueHandle OldValHandle(VMC, OldVal);
00416       OldPN->removeIncomingValue(BB, false);
00417       Value *V = ConvertExpressionToType(OldVal, Ty, VMC, TD);
00418       NewPN->addIncoming(V, BB);
00419     }
00420     Res = NewPN;
00421     break;
00422   }
00423 
00424   case Instruction::Malloc: {
00425     Res = ConvertMallocToType(cast<MallocInst>(I), Ty, Name, VMC, TD);
00426     break;
00427   }
00428 
00429   case Instruction::GetElementPtr: {
00430     // GetElementPtr's are directly convertible to a pointer type if they have
00431     // a number of zeros at the end.  Because removing these values does not
00432     // change the logical offset of the GEP, it is okay and fair to remove them.
00433     // This can change this:
00434     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
00435     //   %t2 = cast %List * * %t1 to %List *
00436     // into
00437     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
00438     // 
00439     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
00440 
00441     // Check to see if there are zero elements that we can remove from the
00442     // index array.  If there are, check to see if removing them causes us to
00443     // get to the right type...
00444     //
00445     std::vector<Value*> Indices(GEP->idx_begin(), GEP->idx_end());
00446     const Type *BaseType = GEP->getPointerOperand()->getType();
00447     const Type *PVTy = cast<PointerType>(Ty)->getElementType();
00448     Res = 0;
00449     while (!Indices.empty() &&
00450            Indices.back() == Constant::getNullValue(Indices.back()->getType())){
00451       Indices.pop_back();
00452       if (GetElementPtrInst::getIndexedType(BaseType, Indices, true) == PVTy) {
00453         if (Indices.size() == 0)
00454           Res = new CastInst(GEP->getPointerOperand(), BaseType); // NOOP CAST
00455         else
00456           Res = new GetElementPtrInst(GEP->getPointerOperand(), Indices, Name);
00457         break;
00458       }
00459     }
00460 
00461     if (Res == 0 && GEP->getNumOperands() == 2 &&
00462         GEP->getType() == PointerType::get(Type::SByteTy)) {
00463       
00464       // Otherwise, we can convert a GEP from one form to the other iff the
00465       // current gep is of the form 'getelementptr sbyte*, unsigned N
00466       // and we could convert this to an appropriate GEP for the new type.
00467       //
00468       const PointerType *NewSrcTy = PointerType::get(PVTy);
00469       BasicBlock::iterator It = I;
00470 
00471       // Check to see if 'N' is an expression that can be converted to
00472       // the appropriate size... if so, allow it.
00473       //
00474       std::vector<Value*> Indices;
00475       const Type *ElTy = ConvertibleToGEP(NewSrcTy, I->getOperand(1),
00476                                           Indices, TD, &It);
00477       if (ElTy) {        
00478         assert(ElTy == PVTy && "Internal error, setup wrong!");
00479         Res = new GetElementPtrInst(Constant::getNullValue(NewSrcTy),
00480                                     Indices, Name);
00481         VMC.ExprMap[I] = Res;
00482         Res->setOperand(0, ConvertExpressionToType(I->getOperand(0),
00483                                                    NewSrcTy, VMC, TD));
00484       }
00485     }
00486 
00487     // Otherwise, it could be that we have something like this:
00488     //     getelementptr [[sbyte] *] * %reg115, uint %reg138    ; [sbyte]**
00489     // and want to convert it into something like this:
00490     //     getelemenptr [[int] *] * %reg115, uint %reg138      ; [int]**
00491     //
00492     if (Res == 0) {
00493       const PointerType *NewSrcTy = PointerType::get(PVTy);
00494       std::vector<Value*> Indices(GEP->idx_begin(), GEP->idx_end());
00495       Res = new GetElementPtrInst(Constant::getNullValue(NewSrcTy),
00496                                   Indices, Name);
00497       VMC.ExprMap[I] = Res;
00498       Res->setOperand(0, ConvertExpressionToType(I->getOperand(0),
00499                                                  NewSrcTy, VMC, TD));
00500     }
00501 
00502 
00503     assert(Res && "Didn't find match!");
00504     break;
00505   }
00506 
00507   case Instruction::Call: {
00508     assert(!isa<Function>(I->getOperand(0)));
00509 
00510     // If this is a function pointer, we can convert the return type if we can
00511     // convert the source function pointer.
00512     //
00513     const PointerType *PT = cast<PointerType>(I->getOperand(0)->getType());
00514     const FunctionType *FT = cast<FunctionType>(PT->getElementType());
00515     std::vector<const Type *> ArgTys(FT->param_begin(), FT->param_end());
00516     const FunctionType *NewTy =
00517       FunctionType::get(Ty, ArgTys, FT->isVarArg());
00518     const PointerType *NewPTy = PointerType::get(NewTy);
00519     if (Ty == Type::VoidTy)
00520       Name = "";  // Make sure not to name calls that now return void!
00521 
00522     Res = new CallInst(Constant::getNullValue(NewPTy),
00523                        std::vector<Value*>(I->op_begin()+1, I->op_end()),
00524                        Name);
00525     VMC.ExprMap[I] = Res;
00526     Res->setOperand(0, ConvertExpressionToType(I->getOperand(0),NewPTy,VMC,TD));
00527     break;
00528   }
00529   default:
00530     assert(0 && "Expression convertible, but don't know how to convert?");
00531     return 0;
00532   }
00533 
00534   assert(Res->getType() == Ty && "Didn't convert expr to correct type!");
00535 
00536   BB->getInstList().insert(I, Res);
00537 
00538   // Add the instruction to the expression map
00539   VMC.ExprMap[I] = Res;
00540 
00541 
00542   unsigned NumUses = I->use_size();
00543   for (unsigned It = 0; It < NumUses; ) {
00544     unsigned OldSize = NumUses;
00545     Value::use_iterator UI = I->use_begin();
00546     std::advance(UI, It);
00547     ConvertOperandToType(*UI, I, Res, VMC, TD);
00548     NumUses = I->use_size();
00549     if (NumUses == OldSize) ++It;
00550   }
00551 
00552   DEBUG(std::cerr << "ExpIn: " << (void*)I << " " << *I
00553                   << "ExpOut: " << (void*)Res << " " << *Res);
00554 
00555   return Res;
00556 }
00557 
00558 
00559 
00560 // ValueConvertibleToType - Return true if it is possible
00561 bool llvm::ValueConvertibleToType(Value *V, const Type *Ty,
00562                                   ValueTypeCache &ConvertedTypes,
00563                                   const TargetData &TD) {
00564   ValueTypeCache::iterator I = ConvertedTypes.find(V);
00565   if (I != ConvertedTypes.end()) return I->second == Ty;
00566   ConvertedTypes[V] = Ty;
00567 
00568   // It is safe to convert the specified value to the specified type IFF all of
00569   // the uses of the value can be converted to accept the new typed value.
00570   //
00571   if (V->getType() != Ty) {
00572     for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I)
00573       if (!OperandConvertibleToType(*I, V, Ty, ConvertedTypes, TD))
00574         return false;
00575   }
00576 
00577   return true;
00578 }
00579 
00580 
00581 
00582 
00583 
00584 // OperandConvertibleToType - Return true if it is possible to convert operand
00585 // V of User (instruction) U to the specified type.  This is true iff it is
00586 // possible to change the specified instruction to accept this.  CTMap is a map
00587 // of converted types, so that circular definitions will see the future type of
00588 // the expression, not the static current type.
00589 //
00590 static bool OperandConvertibleToType(User *U, Value *V, const Type *Ty,
00591                                      ValueTypeCache &CTMap,
00592                                      const TargetData &TD) {
00593   //  if (V->getType() == Ty) return true;   // Operand already the right type?
00594 
00595   // Expression type must be holdable in a register.
00596   if (!Ty->isFirstClassType())
00597     return false;
00598 
00599   Instruction *I = dyn_cast<Instruction>(U);
00600   if (I == 0) return false;              // We can't convert!
00601 
00602   switch (I->getOpcode()) {
00603   case Instruction::Cast:
00604     assert(I->getOperand(0) == V);
00605     // We can convert the expr if the cast destination type is losslessly
00606     // convertible to the requested type.
00607     // Also, do not change a cast that is a noop cast.  For all intents and
00608     // purposes it should be eliminated.
00609     if (!Ty->isLosslesslyConvertibleTo(I->getOperand(0)->getType()) ||
00610         I->getType() == I->getOperand(0)->getType())
00611       return false;
00612 
00613     // Do not allow a 'cast ushort %V to uint' to have it's first operand be
00614     // converted to a 'short' type.  Doing so changes the way sign promotion
00615     // happens, and breaks things.  Only allow the cast to take place if the
00616     // signedness doesn't change... or if the current cast is not a lossy
00617     // conversion.
00618     //
00619     if (!I->getType()->isLosslesslyConvertibleTo(I->getOperand(0)->getType()) &&
00620         I->getOperand(0)->getType()->isSigned() != Ty->isSigned())
00621       return false;
00622 
00623     // We also do not allow conversion of a cast that casts from a ptr to array
00624     // of X to a *X.  For example: cast [4 x %List *] * %val to %List * *
00625     //
00626     if (const PointerType *SPT = 
00627         dyn_cast<PointerType>(I->getOperand(0)->getType()))
00628       if (const PointerType *DPT = dyn_cast<PointerType>(I->getType()))
00629         if (const ArrayType *AT = dyn_cast<ArrayType>(SPT->getElementType()))
00630           if (AT->getElementType() == DPT->getElementType())
00631             return false;
00632     return true;
00633 
00634   case Instruction::Add:
00635     if (isa<PointerType>(Ty)) {
00636       Value *IndexVal = I->getOperand(V == I->getOperand(0) ? 1 : 0);
00637       std::vector<Value*> Indices;
00638       if (const Type *ETy = ConvertibleToGEP(Ty, IndexVal, Indices, TD)) {
00639         const Type *RetTy = PointerType::get(ETy);
00640 
00641         // Only successful if we can convert this type to the required type
00642         if (ValueConvertibleToType(I, RetTy, CTMap, TD)) {
00643           CTMap[I] = RetTy;
00644           return true;
00645         }
00646         // We have to return failure here because ValueConvertibleToType could 
00647         // have polluted our map
00648         return false;
00649       }
00650     }
00651     // FALLTHROUGH
00652   case Instruction::Sub: {
00653     if (!Ty->isInteger() && !Ty->isFloatingPoint()) return false;
00654 
00655     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
00656     return ValueConvertibleToType(I, Ty, CTMap, TD) &&
00657            ExpressionConvertibleToType(OtherOp, Ty, CTMap, TD);
00658   }
00659   case Instruction::SetEQ:
00660   case Instruction::SetNE: {
00661     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
00662     return ExpressionConvertibleToType(OtherOp, Ty, CTMap, TD);
00663   }
00664   case Instruction::Shr:
00665     if (Ty->isSigned() != V->getType()->isSigned()) return false;
00666     // FALL THROUGH
00667   case Instruction::Shl:
00668     if (I->getOperand(1) == V) return false;  // Cannot change shift amount type
00669     if (!Ty->isInteger()) return false;
00670     return ValueConvertibleToType(I, Ty, CTMap, TD);
00671 
00672   case Instruction::Free:
00673     assert(I->getOperand(0) == V);
00674     return isa<PointerType>(Ty);    // Free can free any pointer type!
00675 
00676   case Instruction::Load:
00677     // Cannot convert the types of any subscripts...
00678     if (I->getOperand(0) != V) return false;
00679 
00680     if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
00681       LoadInst *LI = cast<LoadInst>(I);
00682       
00683       const Type *LoadedTy = PT->getElementType();
00684 
00685       // They could be loading the first element of a composite type...
00686       if (const CompositeType *CT = dyn_cast<CompositeType>(LoadedTy)) {
00687         unsigned Offset = 0;     // No offset, get first leaf.
00688         std::vector<Value*> Indices;  // Discarded...
00689         LoadedTy = getStructOffsetType(CT, Offset, Indices, TD, false);
00690         assert(Offset == 0 && "Offset changed from zero???");
00691       }
00692 
00693       if (!LoadedTy->isFirstClassType())
00694         return false;
00695 
00696       if (TD.getTypeSize(LoadedTy) != TD.getTypeSize(LI->getType()))
00697         return false;
00698 
00699       return ValueConvertibleToType(LI, LoadedTy, CTMap, TD);
00700     }
00701     return false;
00702 
00703   case Instruction::Store: {
00704     StoreInst *SI = cast<StoreInst>(I);
00705 
00706     if (V == I->getOperand(0)) {
00707       ValueTypeCache::iterator CTMI = CTMap.find(I->getOperand(1));
00708       if (CTMI != CTMap.end()) {   // Operand #1 is in the table already?
00709         // If so, check to see if it's Ty*, or, more importantly, if it is a
00710         // pointer to a structure where the first element is a Ty... this code
00711         // is necessary because we might be trying to change the source and
00712         // destination type of the store (they might be related) and the dest
00713         // pointer type might be a pointer to structure.  Below we allow pointer
00714         // to structures where the 0th element is compatible with the value,
00715         // now we have to support the symmetrical part of this.
00716         //
00717         const Type *ElTy = cast<PointerType>(CTMI->second)->getElementType();
00718 
00719         // Already a pointer to what we want?  Trivially accept...
00720         if (ElTy == Ty) return true;
00721 
00722         // Tricky case now, if the destination is a pointer to structure,
00723         // obviously the source is not allowed to be a structure (cannot copy
00724         // a whole structure at a time), so the level raiser must be trying to
00725         // store into the first field.  Check for this and allow it now:
00726         //
00727         if (const StructType *SElTy = dyn_cast<StructType>(ElTy)) {
00728           unsigned Offset = 0;
00729           std::vector<Value*> Indices;
00730           ElTy = getStructOffsetType(ElTy, Offset, Indices, TD, false);
00731           assert(Offset == 0 && "Offset changed!");
00732           if (ElTy == 0)    // Element at offset zero in struct doesn't exist!
00733             return false;   // Can only happen for {}*
00734           
00735           if (ElTy == Ty)   // Looks like the 0th element of structure is
00736             return true;    // compatible!  Accept now!
00737 
00738           // Otherwise we know that we can't work, so just stop trying now.
00739           return false;
00740         }
00741       }
00742 
00743       // Can convert the store if we can convert the pointer operand to match
00744       // the new  value type...
00745       return ExpressionConvertibleToType(I->getOperand(1), PointerType::get(Ty),
00746                                          CTMap, TD);
00747     } else if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
00748       const Type *ElTy = PT->getElementType();
00749       assert(V == I->getOperand(1));
00750 
00751       if (isa<StructType>(ElTy)) {
00752         // We can change the destination pointer if we can store our first
00753         // argument into the first element of the structure...
00754         //
00755         unsigned Offset = 0;
00756         std::vector<Value*> Indices;
00757         ElTy = getStructOffsetType(ElTy, Offset, Indices, TD, false);
00758         assert(Offset == 0 && "Offset changed!");
00759         if (ElTy == 0)    // Element at offset zero in struct doesn't exist!
00760           return false;   // Can only happen for {}*
00761       }
00762 
00763       // Must move the same amount of data...
00764       if (!ElTy->isSized() || 
00765           TD.getTypeSize(ElTy) != TD.getTypeSize(I->getOperand(0)->getType()))
00766         return false;
00767 
00768       // Can convert store if the incoming value is convertible and if the
00769       // result will preserve semantics...
00770       const Type *Op0Ty = I->getOperand(0)->getType();
00771       if (!(Op0Ty->isIntegral() ^ ElTy->isIntegral()) &&
00772           !(Op0Ty->isFloatingPoint() ^ ElTy->isFloatingPoint()))
00773         return ExpressionConvertibleToType(I->getOperand(0), ElTy, CTMap, TD);
00774     }
00775     return false;
00776   }
00777 
00778   case Instruction::GetElementPtr:
00779     if (V != I->getOperand(0) || !isa<PointerType>(Ty)) return false;
00780 
00781     // If we have a two operand form of getelementptr, this is really little
00782     // more than a simple addition.  As with addition, check to see if the
00783     // getelementptr instruction can be changed to index into the new type.
00784     //
00785     if (I->getNumOperands() == 2) {
00786       const Type *OldElTy = cast<PointerType>(I->getType())->getElementType();
00787       unsigned DataSize = TD.getTypeSize(OldElTy);
00788       Value *Index = I->getOperand(1);
00789       Instruction *TempScale = 0;
00790 
00791       // If the old data element is not unit sized, we have to create a scale
00792       // instruction so that ConvertibleToGEP will know the REAL amount we are
00793       // indexing by.  Note that this is never inserted into the instruction
00794       // stream, so we have to delete it when we're done.
00795       //
00796       if (DataSize != 1) {
00797         Value *CST;
00798         if (Index->getType()->isSigned())
00799           CST = ConstantSInt::get(Index->getType(), DataSize);
00800         else
00801           CST = ConstantUInt::get(Index->getType(), DataSize);
00802                                   
00803         TempScale = BinaryOperator::create(Instruction::Mul, Index, CST);
00804         Index = TempScale;
00805       }
00806 
00807       // Check to see if the second argument is an expression that can
00808       // be converted to the appropriate size... if so, allow it.
00809       //
00810       std::vector<Value*> Indices;
00811       const Type *ElTy = ConvertibleToGEP(Ty, Index, Indices, TD);
00812       delete TempScale;   // Free our temporary multiply if we made it
00813 
00814       if (ElTy == 0) return false;  // Cannot make conversion...
00815       return ValueConvertibleToType(I, PointerType::get(ElTy), CTMap, TD);
00816     }
00817     return false;
00818 
00819   case Instruction::PHI: {
00820     PHINode *PN = cast<PHINode>(I);
00821     // Be conservative if we find a giant PHI node.
00822     if (PN->getNumIncomingValues() > 32) return false;
00823 
00824     for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i)
00825       if (!ExpressionConvertibleToType(PN->getIncomingValue(i), Ty, CTMap, TD))
00826         return false;
00827     return ValueConvertibleToType(PN, Ty, CTMap, TD);
00828   }
00829 
00830   case Instruction::Call: {
00831     User::op_iterator OI = std::find(I->op_begin(), I->op_end(), V);
00832     assert (OI != I->op_end() && "Not using value!");
00833     unsigned OpNum = OI - I->op_begin();
00834 
00835     // Are we trying to change the function pointer value to a new type?
00836     if (OpNum == 0) {
00837       const PointerType *PTy = dyn_cast<PointerType>(Ty);
00838       if (PTy == 0) return false;  // Can't convert to a non-pointer type...
00839       const FunctionType *FTy = dyn_cast<FunctionType>(PTy->getElementType());
00840       if (FTy == 0) return false;  // Can't convert to a non ptr to function...
00841 
00842       // Do not allow converting to a call where all of the operands are ...'s
00843       if (FTy->getNumParams() == 0 && FTy->isVarArg())
00844         return false;              // Do not permit this conversion!
00845 
00846       // Perform sanity checks to make sure that new function type has the
00847       // correct number of arguments...
00848       //
00849       unsigned NumArgs = I->getNumOperands()-1;  // Don't include function ptr
00850 
00851       // Cannot convert to a type that requires more fixed arguments than
00852       // the call provides...
00853       //
00854       if (NumArgs < FTy->getNumParams()) return false;
00855       
00856       // Unless this is a vararg function type, we cannot provide more arguments
00857       // than are desired...
00858       //
00859       if (!FTy->isVarArg() && NumArgs > FTy->getNumParams())
00860         return false;
00861 
00862       // Okay, at this point, we know that the call and the function type match
00863       // number of arguments.  Now we see if we can convert the arguments
00864       // themselves.  Note that we do not require operands to be convertible,
00865       // we can insert casts if they are convertible but not compatible.  The
00866       // reason for this is that we prefer to have resolved functions but casted
00867       // arguments if possible.
00868       //
00869       for (unsigned i = 0, NA = FTy->getNumParams(); i < NA; ++i)
00870         if (!FTy->getParamType(i)->isLosslesslyConvertibleTo(I->getOperand(i+1)->getType()))
00871           return false;   // Operands must have compatible types!
00872 
00873       // Okay, at this point, we know that all of the arguments can be
00874       // converted.  We succeed if we can change the return type if
00875       // necessary...
00876       //
00877       return ValueConvertibleToType(I, FTy->getReturnType(), CTMap, TD);
00878     }
00879     
00880     const PointerType *MPtr = cast<PointerType>(I->getOperand(0)->getType());
00881     const FunctionType *FTy = cast<FunctionType>(MPtr->getElementType());
00882     if (!FTy->isVarArg()) return false;
00883 
00884     if ((OpNum-1) < FTy->getNumParams())
00885       return false;  // It's not in the varargs section...
00886 
00887     // If we get this far, we know the value is in the varargs section of the
00888     // function!  We can convert if we don't reinterpret the value...
00889     //
00890     return Ty->isLosslesslyConvertibleTo(V->getType());
00891   }
00892   }
00893   return false;
00894 }
00895 
00896 
00897 void llvm::ConvertValueToNewType(Value *V, Value *NewVal, ValueMapCache &VMC,
00898                                  const TargetData &TD) {
00899   ValueHandle VH(VMC, V);
00900 
00901   unsigned NumUses = V->use_size();
00902   for (unsigned It = 0; It < NumUses; ) {
00903     unsigned OldSize = NumUses;
00904     Value::use_iterator UI = V->use_begin();
00905     std::advance(UI, It);
00906     ConvertOperandToType(*UI, V, NewVal, VMC, TD);
00907     NumUses = V->use_size();
00908     if (NumUses == OldSize) ++It;
00909   }
00910 }
00911 
00912 
00913 
00914 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
00915                                  ValueMapCache &VMC, const TargetData &TD) {
00916   if (isa<ValueHandle>(U)) return;  // Valuehandles don't let go of operands...
00917 
00918   if (VMC.OperandsMapped.count(U)) return;
00919   VMC.OperandsMapped.insert(U);
00920 
00921   ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(U);
00922   if (VMCI != VMC.ExprMap.end())
00923     return;
00924 
00925 
00926   Instruction *I = cast<Instruction>(U);  // Only Instructions convertible
00927 
00928   BasicBlock *BB = I->getParent();
00929   assert(BB != 0 && "Instruction not embedded in basic block!");
00930   std::string Name = I->getName();
00931   I->setName("");
00932   Instruction *Res;     // Result of conversion
00933 
00934   //std::cerr << endl << endl << "Type:\t" << Ty << "\nInst: " << I
00935   //          << "BB Before: " << BB << endl;
00936 
00937   // Prevent I from being removed...
00938   ValueHandle IHandle(VMC, I);
00939 
00940   const Type *NewTy = NewVal->getType();
00941   Constant *Dummy = (NewTy != Type::VoidTy) ? 
00942                   Constant::getNullValue(NewTy) : 0;
00943 
00944   switch (I->getOpcode()) {
00945   case Instruction::Cast:
00946     if (VMC.NewCasts.count(ValueHandle(VMC, I))) {
00947       // This cast has already had it's value converted, causing a new cast to
00948       // be created.  We don't want to create YET ANOTHER cast instruction
00949       // representing the original one, so just modify the operand of this cast
00950       // instruction, which we know is newly created.
00951       I->setOperand(0, NewVal);
00952       I->setName(Name);  // give I its name back
00953       return;
00954 
00955     } else {
00956       Res = new CastInst(NewVal, I->getType(), Name);
00957     }
00958     break;
00959 
00960   case Instruction::Add:
00961     if (isa<PointerType>(NewTy)) {
00962       Value *IndexVal = I->getOperand(OldVal == I->getOperand(0) ? 1 : 0);
00963       std::vector<Value*> Indices;
00964       BasicBlock::iterator It = I;
00965 
00966       if (const Type *ETy = ConvertibleToGEP(NewTy, IndexVal, Indices, TD,&It)){
00967         // If successful, convert the add to a GEP
00968         //const Type *RetTy = PointerType::get(ETy);
00969         // First operand is actually the given pointer...
00970         Res = new GetElementPtrInst(NewVal, Indices, Name);
00971         assert(cast<PointerType>(Res->getType())->getElementType() == ETy &&
00972                "ConvertibleToGEP broken!");
00973         break;
00974       }
00975     }
00976     // FALLTHROUGH
00977 
00978   case Instruction::Sub:
00979   case Instruction::SetEQ:
00980   case Instruction::SetNE: {
00981     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
00982                                  Dummy, Dummy, Name);
00983     VMC.ExprMap[I] = Res;   // Add node to expression eagerly
00984 
00985     unsigned OtherIdx = (OldVal == I->getOperand(0)) ? 1 : 0;
00986     Value *OtherOp    = I->getOperand(OtherIdx);
00987     Res->setOperand(!OtherIdx, NewVal);
00988     Value *NewOther   = ConvertExpressionToType(OtherOp, NewTy, VMC, TD);
00989     Res->setOperand(OtherIdx, NewOther);
00990     break;
00991   }
00992   case Instruction::Shl:
00993   case Instruction::Shr:
00994     assert(I->getOperand(0) == OldVal);
00995     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), NewVal,
00996                         I->getOperand(1), Name);
00997     break;
00998 
00999   case Instruction::Free:            // Free can free any pointer type!
01000     assert(I->getOperand(0) == OldVal);
01001     Res = new FreeInst(NewVal);
01002     break;
01003 
01004 
01005   case Instruction::Load: {
01006     assert(I->getOperand(0) == OldVal && isa<PointerType>(NewVal->getType()));
01007     const Type *LoadedTy =
01008       cast<PointerType>(NewVal->getType())->getElementType();
01009 
01010     Value *Src = NewVal;
01011 
01012     if (const CompositeType *CT = dyn_cast<CompositeType>(LoadedTy)) {
01013       std::vector<Value*> Indices;
01014       Indices.push_back(Constant::getNullValue(Type::UIntTy));
01015 
01016       unsigned Offset = 0;   // No offset, get first leaf.
01017       LoadedTy = getStructOffsetType(CT, Offset, Indices, TD, false);
01018       assert(LoadedTy->isFirstClassType());
01019 
01020       if (Indices.size() != 1) {     // Do not generate load X, 0
01021         // Insert the GEP instruction before this load.
01022         Src = new GetElementPtrInst(Src, Indices, Name+".idx", I);
01023       }
01024     }
01025     
01026     Res = new LoadInst(Src, Name);
01027     assert(Res->getType()->isFirstClassType() && "Load of structure or array!");
01028     break;
01029   }
01030 
01031   case Instruction::Store: {
01032     if (I->getOperand(0) == OldVal) {  // Replace the source value
01033       // Check to see if operand #1 has already been converted...
01034       ValueMapCache::ExprMapTy::iterator VMCI =
01035         VMC.ExprMap.find(I->getOperand(1));
01036       if (VMCI != VMC.ExprMap.end()) {
01037         // Comments describing this stuff are in the OperandConvertibleToType
01038         // switch statement for Store...
01039         //
01040         const Type *ElTy =
01041           cast<PointerType>(VMCI->second->getType())->getElementType();
01042         
01043         Value *SrcPtr = VMCI->second;
01044 
01045         if (ElTy != NewTy) {
01046           // We check that this is a struct in the initial scan...
01047           const StructType *SElTy = cast<StructType>(ElTy);
01048           
01049           std::vector<Value*> Indices;
01050           Indices.push_back(Constant::getNullValue(Type::UIntTy));
01051 
01052           unsigned Offset = 0;
01053           const Type *Ty = getStructOffsetType(ElTy, Offset, Indices, TD,false);
01054           assert(Offset == 0 && "Offset changed!");
01055           assert(NewTy == Ty && "Did not convert to correct type!");
01056 
01057           // Insert the GEP instruction before this store.
01058           SrcPtr = new GetElementPtrInst(SrcPtr, Indices,
01059                                          SrcPtr->getName()+".idx", I);
01060         }
01061         Res = new StoreInst(NewVal, SrcPtr);
01062 
01063         VMC.ExprMap[I] = Res;
01064       } else {
01065         // Otherwise, we haven't converted Operand #1 over yet...
01066         const PointerType *NewPT = PointerType::get(NewTy);
01067         Res = new StoreInst(NewVal, Constant::getNullValue(NewPT));
01068         VMC.ExprMap[I] = Res;
01069         Res->setOperand(1, ConvertExpressionToType(I->getOperand(1),
01070                                                    NewPT, VMC, TD));
01071       }
01072     } else {                           // Replace the source pointer
01073       const Type *ValTy = cast<PointerType>(NewTy)->getElementType();
01074 
01075       Value *SrcPtr = NewVal;
01076 
01077       if (isa<StructType>(ValTy)) {
01078         std::vector<Value*> Indices;
01079         Indices.push_back(Constant::getNullValue(Type::UIntTy));
01080 
01081         unsigned Offset = 0;
01082         ValTy = getStructOffsetType(ValTy, Offset, Indices, TD, false);
01083 
01084         assert(Offset == 0 && ValTy);
01085 
01086         // Insert the GEP instruction before this store.
01087         SrcPtr = new GetElementPtrInst(SrcPtr, Indices,
01088                                        SrcPtr->getName()+".idx", I);
01089       }
01090 
01091       Res = new StoreInst(Constant::getNullValue(ValTy), SrcPtr);
01092       VMC.ExprMap[I] = Res;
01093       Res->setOperand(0, ConvertExpressionToType(I->getOperand(0),
01094                                                  ValTy, VMC, TD));
01095     }
01096     break;
01097   }
01098 
01099 
01100   case Instruction::GetElementPtr: {
01101     // Convert a one index getelementptr into just about anything that is
01102     // desired.
01103     //
01104     BasicBlock::iterator It = I;
01105     const Type *OldElTy = cast<PointerType>(I->getType())->getElementType();
01106     unsigned DataSize = TD.getTypeSize(OldElTy);
01107     Value *Index = I->getOperand(1);
01108 
01109     if (DataSize != 1) {
01110       // Insert a multiply of the old element type is not a unit size...
01111       Value *CST;
01112       if (Index->getType()->isSigned())
01113         CST = ConstantSInt::get(Index->getType(), DataSize);
01114       else
01115         CST = ConstantUInt::get(Index->getType(), DataSize);
01116 
01117       Index = BinaryOperator::create(Instruction::Mul, Index, CST, "scale", It);
01118     }
01119 
01120     // Perform the conversion now...
01121     //
01122     std::vector<Value*> Indices;
01123     const Type *ElTy = ConvertibleToGEP(NewVal->getType(),Index,Indices,TD,&It);
01124     assert(ElTy != 0 && "GEP Conversion Failure!");
01125     Res = new GetElementPtrInst(NewVal, Indices, Name);
01126     assert(Res->getType() == PointerType::get(ElTy) &&
01127            "ConvertibleToGet failed!");
01128   }
01129 #if 0
01130     if (I->getType() == PointerType::get(Type::SByteTy)) {
01131       // Convert a getelementptr sbyte * %reg111, uint 16 freely back to
01132       // anything that is a pointer type...
01133       //
01134       BasicBlock::iterator It = I;
01135     
01136       // Check to see if the second argument is an expression that can
01137       // be converted to the appropriate size... if so, allow it.
01138       //
01139       std::vector<Value*> Indices;
01140       const Type *ElTy = ConvertibleToGEP(NewVal->getType(), I->getOperand(1),
01141                                           Indices, TD, &It);
01142       assert(ElTy != 0 && "GEP Conversion Failure!");
01143       
01144       Res = new GetElementPtrInst(NewVal, Indices, Name);
01145     } else {
01146       // Convert a getelementptr ulong * %reg123, uint %N
01147       // to        getelementptr  long * %reg123, uint %N
01148       // ... where the type must simply stay the same size...
01149       //
01150       GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
01151       std::vector<Value*> Indices(GEP->idx_begin(), GEP->idx_end());
01152       Res = new GetElementPtrInst(NewVal, Indices, Name);
01153     }
01154 #endif
01155     break;
01156 
01157   case Instruction::PHI: {
01158     PHINode *OldPN = cast<PHINode>(I);
01159     PHINode *NewPN = new PHINode(NewTy, Name);
01160     VMC.ExprMap[I] = NewPN;
01161 
01162     while (OldPN->getNumOperands()) {
01163       BasicBlock *BB = OldPN->getIncomingBlock(0);
01164       Value *OldVal = OldPN->getIncomingValue(0);
01165       ValueHandle OldValHandle(VMC, OldVal);
01166       OldPN->removeIncomingValue(BB, false);
01167       Value *V = ConvertExpressionToType(OldVal, NewTy, VMC, TD);
01168       NewPN->addIncoming(V, BB);
01169     }
01170     Res = NewPN;
01171     break;
01172   }
01173 
01174   case Instruction::Call: {
01175     Value *Meth = I->getOperand(0);
01176     std::vector<Value*> Params(I->op_begin()+1, I->op_end());
01177 
01178     if (Meth == OldVal) {   // Changing the function pointer?
01179       const PointerType *NewPTy = cast<PointerType>(NewVal->getType());
01180       const FunctionType *NewTy = cast<FunctionType>(NewPTy->getElementType());
01181 
01182       if (NewTy->getReturnType() == Type::VoidTy)
01183         Name = "";  // Make sure not to name a void call!
01184 
01185       // Get an iterator to the call instruction so that we can insert casts for
01186       // operands if need be.  Note that we do not require operands to be
01187       // convertible, we can insert casts if they are convertible but not
01188       // compatible.  The reason for this is that we prefer to have resolved
01189       // functions but casted arguments if possible.
01190       //
01191       BasicBlock::iterator It = I;
01192 
01193       // Convert over all of the call operands to their new types... but only
01194       // convert over the part that is not in the vararg section of the call.
01195       //
01196       for (unsigned i = 0; i != NewTy->getNumParams(); ++i)
01197         if (Params[i]->getType() != NewTy->getParamType(i)) {
01198           // Create a cast to convert it to the right type, we know that this
01199           // is a lossless cast...
01200           //
01201           Params[i] = new CastInst(Params[i], NewTy->getParamType(i),
01202                                    "callarg.cast." +
01203                                    Params[i]->getName(), It);
01204         }
01205       Meth = NewVal;  // Update call destination to new value
01206 
01207     } else {                   // Changing an argument, must be in vararg area
01208       std::vector<Value*>::iterator OI =
01209         std::find(Params.begin(), Params.end(), OldVal);
01210       assert (OI != Params.end() && "Not using value!");
01211 
01212       *OI = NewVal;
01213     }
01214 
01215     Res = new CallInst(Meth, Params, Name);
01216     break;
01217   }
01218   default:
01219     assert(0 && "Expression convertible, but don't know how to convert?");
01220     return;
01221   }
01222 
01223   // If the instruction was newly created, insert it into the instruction
01224   // stream.
01225   //
01226   BasicBlock::iterator It = I;
01227   assert(It != BB->end() && "Instruction not in own basic block??");
01228   BB->getInstList().insert(It, Res);   // Keep It pointing to old instruction
01229 
01230   DEBUG(std::cerr << "COT CREATED: "  << (void*)Res << " " << *Res
01231                   << "In: " << (void*)I << " " << *I << "Out: " << (void*)Res
01232                   << " " << *Res);
01233 
01234   // Add the instruction to the expression map
01235   VMC.ExprMap[I] = Res;
01236 
01237   if (I->getType() != Res->getType())
01238     ConvertValueToNewType(I, Res, VMC, TD);
01239   else {
01240     bool FromStart = true;
01241     Value::use_iterator UI;
01242     while (1) {
01243       if (FromStart) UI = I->use_begin();
01244       if (UI == I->use_end()) break;
01245       
01246       if (isa<ValueHandle>(*UI)) {
01247         ++UI;
01248         FromStart = false;
01249       } else {
01250         User *U = *UI;
01251         if (!FromStart) --UI;
01252         U->replaceUsesOfWith(I, Res);
01253         if (!FromStart) ++UI;
01254       }
01255     }
01256   }
01257 }
01258 
01259 
01260 ValueHandle::ValueHandle(ValueMapCache &VMC, Value *V)
01261   : Instruction(Type::VoidTy, UserOp1, ""), Cache(VMC) {
01262   //DEBUG(std::cerr << "VH AQUIRING: " << (void*)V << " " << V);
01263   Operands.push_back(Use(V, this));
01264 }
01265 
01266 ValueHandle::ValueHandle(const ValueHandle &VH)
01267   : Instruction(Type::VoidTy, UserOp1, ""), Cache(VH.Cache) {
01268   //DEBUG(std::cerr << "VH AQUIRING: " << (void*)V << " " << V);
01269   Operands.push_back(Use((Value*)VH.getOperand(0), this));
01270 }
01271 
01272 static void RecursiveDelete(ValueMapCache &Cache, Instruction *I) {
01273   if (!I || !I->use_empty()) return;
01274 
01275   assert(I->getParent() && "Inst not in basic block!");
01276 
01277   //DEBUG(std::cerr << "VH DELETING: " << (void*)I << " " << I);
01278 
01279   for (User::op_iterator OI = I->op_begin(), OE = I->op_end(); 
01280        OI != OE; ++OI)
01281     if (Instruction *U = dyn_cast<Instruction>(OI)) {
01282       *OI = 0;
01283       RecursiveDelete(Cache, U);
01284     }
01285 
01286   I->getParent()->getInstList().remove(I);
01287 
01288   Cache.OperandsMapped.erase(I);
01289   Cache.ExprMap.erase(I);
01290   delete I;
01291 }
01292 
01293 ValueHandle::~ValueHandle() {
01294   if (Operands[0]->hasOneUse()) {
01295     Value *V = Operands[0];
01296     Operands[0] = 0;   // Drop use!
01297 
01298     // Now we just need to remove the old instruction so we don't get infinite
01299     // loops.  Note that we cannot use DCE because DCE won't remove a store
01300     // instruction, for example.
01301     //
01302     RecursiveDelete(Cache, dyn_cast<Instruction>(V));
01303   } else {
01304     //DEBUG(std::cerr << "VH RELEASING: " << (void*)Operands[0].get() << " "
01305     //                << Operands[0]->use_size() << " " << Operands[0]);
01306   }
01307 }
01308