lib/Transforms/ExprTypeConvert.cpp

   1 //===- ExprTypeConvert.cpp - Code to change an LLVM Expr Type ---------------=//
   2 //
   3 // This file implements the part of level raising that checks to see if it is
   4 // possible to coerce an entire expression tree into a different type.  If
   5 // convertable, other routines from this file will do the conversion.
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "TransformInternals.h"
  10 #include "llvm/Function.h"
  11 #include "llvm/iOther.h"
  12 #include "llvm/iPHINode.h"
  13 #include "llvm/iMemory.h"
  14 #include "llvm/Constants.h"
  15 #include "llvm/ConstantHandling.h"
  16 #include "llvm/Transforms/Scalar/DCE.h"
  17 #include "llvm/Analysis/Expressions.h"
  18 #include "Support/STLExtras.h"
  19 #include <map>
  20 #include <algorithm>
  21 #include <iostream>
  22 using std::cerr;
  23
  24 //#define DEBUG_EXPR_CONVERT 1
  25
  26 static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
  27                                      ValueTypeCache &ConvertedTypes);
  28
  29 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
  30                                  ValueMapCache &VMC);
  31
  32 // AllIndicesZero - Return true if all of the indices of the specified memory
  33 // access instruction are zero, indicating an effectively nil offset to the
  34 // pointer value.
  35 //
  36 static bool AllIndicesZero(const MemAccessInst *MAI) {
  37   for (User::const_op_iterator S = MAI->idx_begin(), E = MAI->idx_end();
  38        S != E; ++S)
  39     if (!isa<Constant>(*S) || !cast<Constant>(*S)->isNullValue())
  40       return false;
  41   return true;
  42 }
  43
  44
  45 // Peephole Malloc instructions: we take a look at the use chain of the
  46 // malloc instruction, and try to find out if the following conditions hold:
  47 //   1. The malloc is of the form: 'malloc [sbyte], uint <constant>'
  48 //   2. The only users of the malloc are cast & add instructions
  49 //   3. Of the cast instructions, there is only one destination pointer type
  50 //      [RTy] where the size of the pointed to object is equal to the number
  51 //      of bytes allocated.
  52 //
  53 // If these conditions hold, we convert the malloc to allocate an [RTy]
  54 // element.  TODO: This comment is out of date WRT arrays
  55 //
  56 static bool MallocConvertableToType(MallocInst *MI, const Type *Ty,
  57                                     ValueTypeCache &CTMap) {
  58   if (!isa<PointerType>(Ty)) return false;   // Malloc always returns pointers
  59
  60   // Deal with the type to allocate, not the pointer type...
  61   Ty = cast<PointerType>(Ty)->getElementType();
  62   if (!Ty->isSized()) return false;      // Can only alloc something with a size
  63
  64   // Analyze the number of bytes allocated...
  65   analysis::ExprType Expr = analysis::ClassifyExpression(MI->getArraySize());
  66
  67   // Get information about the base datatype being allocated, before & after
  68   unsigned ReqTypeSize = TD.getTypeSize(Ty);
  69   unsigned OldTypeSize = TD.getTypeSize(MI->getType()->getElementType());
  70
  71   // Must have a scale or offset to analyze it...
  72   if (!Expr.Offset && !Expr.Scale && OldTypeSize == 1) return false;
  73
  74   // Get the offset and scale of the allocation...
  75   int OffsetVal = Expr.Offset ? getConstantValue(Expr.Offset) : 0;
  76   int ScaleVal = Expr.Scale ? getConstantValue(Expr.Scale) : (Expr.Var ? 1 : 0);
  77   if (ScaleVal < 0 || OffsetVal < 0) {
  78     cerr << "malloc of a negative number???\n";
  79     return false;
  80   }
  81
  82   // The old type might not be of unit size, take old size into consideration
  83   // here...
  84   unsigned Offset = (unsigned)OffsetVal * OldTypeSize;
  85   unsigned Scale  = (unsigned)ScaleVal  * OldTypeSize;
  86
  87   // In order to be successful, both the scale and the offset must be a multiple
  88   // of the requested data type's size.
  89   //
  90   if (Offset/ReqTypeSize*ReqTypeSize != Offset ||
  91       Scale/ReqTypeSize*ReqTypeSize != Scale)
  92     return false;   // Nope.
  93
  94   return true;
  95 }
  96
  97 static Instruction *ConvertMallocToType(MallocInst *MI, const Type *Ty,
  98                                         const std::string &Name,
  99                                         ValueMapCache &VMC){
 100   BasicBlock *BB = MI->getParent();
 101   BasicBlock::iterator It = BB->end();
 102
 103   // Analyze the number of bytes allocated...
 104   analysis::ExprType Expr = analysis::ClassifyExpression(MI->getArraySize());
 105
 106   const PointerType *AllocTy = cast<PointerType>(Ty);
 107   const Type *ElType = AllocTy->getElementType();
 108
 109   unsigned DataSize = TD.getTypeSize(ElType);
 110   unsigned OldTypeSize = TD.getTypeSize(MI->getType()->getElementType());
 111
 112   // Get the offset and scale coefficients that we are allocating...
 113   int OffsetVal = (Expr.Offset ? getConstantValue(Expr.Offset) : 0);
 114   int ScaleVal = Expr.Scale ? getConstantValue(Expr.Scale) : (Expr.Var ? 1 : 0);
 115
 116   // The old type might not be of unit size, take old size into consideration
 117   // here...
 118   unsigned Offset = (unsigned)OffsetVal * OldTypeSize / DataSize;
 119   unsigned Scale  = (unsigned)ScaleVal  * OldTypeSize / DataSize;
 120
 121   // Locate the malloc instruction, because we may be inserting instructions
 122   It = find(BB->getInstList().begin(), BB->getInstList().end(), MI);
 123
 124   // If we have a scale, apply it first...
 125   if (Expr.Var) {
 126     // Expr.Var is not neccesarily unsigned right now, insert a cast now.
 127     if (Expr.Var->getType() != Type::UIntTy) {
 128       Instruction *CI = new CastInst(Expr.Var, Type::UIntTy);
 129       if (Expr.Var->hasName()) CI->setName(Expr.Var->getName()+"-uint");
 130       It = BB->getInstList().insert(It, CI)+1;
 131       Expr.Var = CI;
 132     }
 133
 134     if (Scale != 1) {
 135       Instruction *ScI =
 136         BinaryOperator::create(Instruction::Mul, Expr.Var,
 137                                ConstantUInt::get(Type::UIntTy, Scale));
 138       if (Expr.Var->hasName()) ScI->setName(Expr.Var->getName()+"-scl");
 139       It = BB->getInstList().insert(It, ScI)+1;
 140       Expr.Var = ScI;
 141     }
 142
 143   } else {
 144     // If we are not scaling anything, just make the offset be the "var"...
 145     Expr.Var = ConstantUInt::get(Type::UIntTy, Offset);
 146     Offset = 0; Scale = 1;
 147   }
 148
 149   // If we have an offset now, add it in...
 150   if (Offset != 0) {
 151     assert(Expr.Var && "Var must be nonnull by now!");
 152
 153     Instruction *AddI =
 154       BinaryOperator::create(Instruction::Add, Expr.Var,
 155                              ConstantUInt::get(Type::UIntTy, Offset));
 156     if (Expr.Var->hasName()) AddI->setName(Expr.Var->getName()+"-off");
 157     It = BB->getInstList().insert(It, AddI)+1;
 158     Expr.Var = AddI;
 159   }
 160
 161   Instruction *NewI = new MallocInst(AllocTy, Expr.Var, Name);
 162
 163   assert(AllocTy == Ty);
 164   return NewI;
 165 }
 166
 167
 168 // ExpressionConvertableToType - Return true if it is possible
 169 bool ExpressionConvertableToType(Value *V, const Type *Ty,
 170                                  ValueTypeCache &CTMap) {
 171   if (V->getType() == Ty) return true;  // Expression already correct type!
 172
 173   // Expression type must be holdable in a register.
 174   if (!Ty->isFirstClassType())
 175     return false;
 176
 177   ValueTypeCache::iterator CTMI = CTMap.find(V);
 178   if (CTMI != CTMap.end()) return CTMI->second == Ty;
 179
 180   CTMap[V] = Ty;
 181
 182   Instruction *I = dyn_cast<Instruction>(V);
 183   if (I == 0) {
 184     // It's not an instruction, check to see if it's a constant... all constants
 185     // can be converted to an equivalent value (except pointers, they can't be
 186     // const prop'd in general).  We just ask the constant propogator to see if
 187     // it can convert the value...
 188     //
 189     if (Constant *CPV = dyn_cast<Constant>(V))
 190       if (ConstantFoldCastInstruction(CPV, Ty))
 191         return true;  // Don't worry about deallocating, it's a constant.
 192
 193     return false;              // Otherwise, we can't convert!
 194   }
 195
 196   switch (I->getOpcode()) {
 197   case Instruction::Cast:
 198     // We can convert the expr if the cast destination type is losslessly
 199     // convertable to the requested type.
 200     if (!Ty->isLosslesslyConvertableTo(I->getType())) return false;
 201 #if 1
 202     // We also do not allow conversion of a cast that casts from a ptr to array
 203     // of X to a *X.  For example: cast [4 x %List *] * %val to %List * *
 204     //
 205     if (PointerType *SPT = dyn_cast<PointerType>(I->getOperand(0)->getType()))
 206       if (PointerType *DPT = dyn_cast<PointerType>(I->getType()))
 207         if (ArrayType *AT = dyn_cast<ArrayType>(SPT->getElementType()))
 208           if (AT->getElementType() == DPT->getElementType())
 209             return false;
 210 #endif
 211     break;
 212
 213   case Instruction::Add:
 214   case Instruction::Sub:
 215     if (!ExpressionConvertableToType(I->getOperand(0), Ty, CTMap) ||
 216         !ExpressionConvertableToType(I->getOperand(1), Ty, CTMap))
 217       return false;
 218     break;
 219   case Instruction::Shr:
 220     if (Ty->isSigned() != V->getType()->isSigned()) return false;
 221     // FALL THROUGH
 222   case Instruction::Shl:
 223     if (!ExpressionConvertableToType(I->getOperand(0), Ty, CTMap))
 224       return false;
 225     break;
 226
 227   case Instruction::Load: {
 228     LoadInst *LI = cast<LoadInst>(I);
 229     if (LI->hasIndices() && !AllIndicesZero(LI)) {
 230       // We can't convert a load expression if it has indices... unless they are
 231       // all zero.
 232       return false;
 233     }
 234
 235     if (!ExpressionConvertableToType(LI->getPointerOperand(),
 236                                      PointerType::get(Ty), CTMap))
 237       return false;
 238     break;
 239   }
 240   case Instruction::PHINode: {
 241     PHINode *PN = cast<PHINode>(I);
 242     for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i)
 243       if (!ExpressionConvertableToType(PN->getIncomingValue(i), Ty, CTMap))
 244         return false;
 245     break;
 246   }
 247
 248   case Instruction::Malloc:
 249     if (!MallocConvertableToType(cast<MallocInst>(I), Ty, CTMap))
 250       return false;
 251     break;
 252
 253 #if 1
 254   case Instruction::GetElementPtr: {
 255     // GetElementPtr's are directly convertable to a pointer type if they have
 256     // a number of zeros at the end.  Because removing these values does not
 257     // change the logical offset of the GEP, it is okay and fair to remove them.
 258     // This can change this:
 259     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 260     //   %t2 = cast %List * * %t1 to %List *
 261     // into
 262     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 263     //
 264     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 265     const PointerType *PTy = dyn_cast<PointerType>(Ty);
 266     if (!PTy) return false;  // GEP must always return a pointer...
 267     const Type *PVTy = PTy->getElementType();
 268
 269     // Check to see if there are zero elements that we can remove from the
 270     // index array.  If there are, check to see if removing them causes us to
 271     // get to the right type...
 272     //
 273     std::vector<Value*> Indices = GEP->copyIndices();
 274     const Type *BaseType = GEP->getPointerOperand()->getType();
 275     const Type *ElTy = 0;
 276
 277     while (!Indices.empty() && isa<ConstantUInt>(Indices.back()) &&
 278            cast<ConstantUInt>(Indices.back())->getValue() == 0) {
 279       Indices.pop_back();
 280       ElTy = GetElementPtrInst::getIndexedType(BaseType, Indices, true);
 281       if (ElTy == PVTy)
 282         break;  // Found a match!!
 283       ElTy = 0;
 284     }
 285
 286     if (ElTy) break;   // Found a number of zeros we can strip off!
 287
 288     // Otherwise, we can convert a GEP from one form to the other iff the
 289     // current gep is of the form 'getelementptr sbyte*, unsigned N
 290     // and we could convert this to an appropriate GEP for the new type.
 291     //
 292     if (GEP->getNumOperands() == 2 &&
 293         GEP->getOperand(1)->getType() == Type::UIntTy &&
 294         GEP->getType() == PointerType::get(Type::SByteTy)) {
 295
 296       // Do not Check to see if our incoming pointer can be converted
 297       // to be a ptr to an array of the right type... because in more cases than
 298       // not, it is simply not analyzable because of pointer/array
 299       // discrepencies.  To fix this, we will insert a cast before the GEP.
 300       //
 301
 302       // Check to see if 'N' is an expression that can be converted to
 303       // the appropriate size... if so, allow it.
 304       //
 305       std::vector<Value*> Indices;
 306       const Type *ElTy = ConvertableToGEP(PTy, I->getOperand(1), Indices);
 307       if (ElTy == PVTy) {
 308         if (!ExpressionConvertableToType(I->getOperand(0),
 309                                          PointerType::get(ElTy), CTMap))
 310           return false;  // Can't continue, ExConToTy might have polluted set!
 311         break;
 312       }
 313     }
 314
 315     // Otherwise, it could be that we have something like this:
 316     //     getelementptr [[sbyte] *] * %reg115, uint %reg138    ; [sbyte]**
 317     // and want to convert it into something like this:
 318     //     getelemenptr [[int] *] * %reg115, uint %reg138      ; [int]**
 319     //
 320     if (GEP->getNumOperands() == 2 &&
 321         GEP->getOperand(1)->getType() == Type::UIntTy &&
 322         TD.getTypeSize(PTy->getElementType()) ==
 323         TD.getTypeSize(GEP->getType()->getElementType())) {
 324       const PointerType *NewSrcTy = PointerType::get(PVTy);
 325       if (!ExpressionConvertableToType(I->getOperand(0), NewSrcTy, CTMap))
 326         return false;
 327       break;
 328     }
 329
 330     return false;   // No match, maybe next time.
 331   }
 332 #endif
 333
 334   default:
 335     return false;
 336   }
 337
 338   // Expressions are only convertable if all of the users of the expression can
 339   // have this value converted.  This makes use of the map to avoid infinite
 340   // recursion.
 341   //
 342   for (Value::use_iterator It = I->use_begin(), E = I->use_end(); It != E; ++It)
 343     if (!OperandConvertableToType(*It, I, Ty, CTMap))
 344       return false;
 345
 346   return true;
 347 }
 348
 349
 350 Value *ConvertExpressionToType(Value *V, const Type *Ty, ValueMapCache &VMC) {
 351   if (V->getType() == Ty) return V;  // Already where we need to be?
 352
 353   ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(V);
 354   if (VMCI != VMC.ExprMap.end()) {
 355     assert(VMCI->second->getType() == Ty);
 356
 357     if (Instruction *I = dyn_cast<Instruction>(V))
 358       ValueHandle IHandle(VMC, I);  // Remove I if it is unused now!
 359
 360     return VMCI->second;
 361   }
 362
 363 #ifdef DEBUG_EXPR_CONVERT
 364   cerr << "CETT: " << (void*)V << " " << V;
 365 #endif
 366
 367   Instruction *I = dyn_cast<Instruction>(V);
 368   if (I == 0)
 369     if (Constant *CPV = cast<Constant>(V)) {
 370       // Constants are converted by constant folding the cast that is required.
 371       // We assume here that all casts are implemented for constant prop.
 372       Value *Result = ConstantFoldCastInstruction(CPV, Ty);
 373       assert(Result && "ConstantFoldCastInstruction Failed!!!");
 374       assert(Result->getType() == Ty && "Const prop of cast failed!");
 375
 376       // Add the instruction to the expression map
 377       VMC.ExprMap[V] = Result;
 378       return Result;
 379     }
 380
 381
 382   BasicBlock *BB = I->getParent();
 383   BasicBlock::InstListType &BIL = BB->getInstList();
 384   std::string Name = I->getName();  if (!Name.empty()) I->setName("");
 385   Instruction *Res;     // Result of conversion
 386
 387   ValueHandle IHandle(VMC, I);  // Prevent I from being removed!
 388
 389   Constant *Dummy = Constant::getNullValue(Ty);
 390
 391   switch (I->getOpcode()) {
 392   case Instruction::Cast:
 393     Res = new CastInst(I->getOperand(0), Ty, Name);
 394     break;
 395
 396   case Instruction::Add:
 397   case Instruction::Sub:
 398     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
 399                                  Dummy, Dummy, Name);
 400     VMC.ExprMap[I] = Res;   // Add node to expression eagerly
 401
 402     Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC));
 403     Res->setOperand(1, ConvertExpressionToType(I->getOperand(1), Ty, VMC));
 404     break;
 405
 406   case Instruction::Shl:
 407   case Instruction::Shr:
 408     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), Dummy,
 409                         I->getOperand(1), Name);
 410     VMC.ExprMap[I] = Res;
 411     Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC));
 412     break;
 413
 414   case Instruction::Load: {
 415     LoadInst *LI = cast<LoadInst>(I);
 416     assert(!LI->hasIndices() || AllIndicesZero(LI));
 417
 418     Res = new LoadInst(Constant::getNullValue(PointerType::get(Ty)), Name);
 419     VMC.ExprMap[I] = Res;
 420     Res->setOperand(0, ConvertExpressionToType(LI->getPointerOperand(),
 421                                                PointerType::get(Ty), VMC));
 422     assert(Res->getOperand(0)->getType() == PointerType::get(Ty));
 423     assert(Ty == Res->getType());
 424     assert(Res->getType()->isFirstClassType() && "Load of structure or array!");
 425     break;
 426   }
 427
 428   case Instruction::PHINode: {
 429     PHINode *OldPN = cast<PHINode>(I);
 430     PHINode *NewPN = new PHINode(Ty, Name);
 431
 432     VMC.ExprMap[I] = NewPN;   // Add node to expression eagerly
 433     while (OldPN->getNumOperands()) {
 434       BasicBlock *BB = OldPN->getIncomingBlock(0);
 435       Value *OldVal = OldPN->getIncomingValue(0);
 436       ValueHandle OldValHandle(VMC, OldVal);
 437       OldPN->removeIncomingValue(BB);
 438       Value *V = ConvertExpressionToType(OldVal, Ty, VMC);
 439       NewPN->addIncoming(V, BB);
 440     }
 441     Res = NewPN;
 442     break;
 443   }
 444
 445   case Instruction::Malloc: {
 446     Res = ConvertMallocToType(cast<MallocInst>(I), Ty, Name, VMC);
 447     break;
 448   }
 449
 450   case Instruction::GetElementPtr: {
 451     // GetElementPtr's are directly convertable to a pointer type if they have
 452     // a number of zeros at the end.  Because removing these values does not
 453     // change the logical offset of the GEP, it is okay and fair to remove them.
 454     // This can change this:
 455     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 456     //   %t2 = cast %List * * %t1 to %List *
 457     // into
 458     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 459     //
 460     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 461
 462     // Check to see if there are zero elements that we can remove from the
 463     // index array.  If there are, check to see if removing them causes us to
 464     // get to the right type...
 465     //
 466     std::vector<Value*> Indices = GEP->copyIndices();
 467     const Type *BaseType = GEP->getPointerOperand()->getType();
 468     const Type *PVTy = cast<PointerType>(Ty)->getElementType();
 469     Res = 0;
 470     while (!Indices.empty() && isa<ConstantUInt>(Indices.back()) &&
 471            cast<ConstantUInt>(Indices.back())->getValue() == 0) {
 472       Indices.pop_back();
 473       if (GetElementPtrInst::getIndexedType(BaseType, Indices, true) == PVTy) {
 474         if (Indices.size() == 0) {
 475           Res = new CastInst(GEP->getPointerOperand(), BaseType); // NOOP
 476         } else {
 477           Res = new GetElementPtrInst(GEP->getPointerOperand(), Indices, Name);
 478         }
 479         break;
 480       }
 481     }
 482
 483     if (Res == 0 && GEP->getNumOperands() == 2 &&
 484         GEP->getOperand(1)->getType() == Type::UIntTy &&
 485         GEP->getType() == PointerType::get(Type::SByteTy)) {
 486
 487       // Otherwise, we can convert a GEP from one form to the other iff the
 488       // current gep is of the form 'getelementptr [sbyte]*, unsigned N
 489       // and we could convert this to an appropriate GEP for the new type.
 490       //
 491       const PointerType *NewSrcTy = PointerType::get(PVTy);
 492       BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 493
 494       // Check to see if 'N' is an expression that can be converted to
 495       // the appropriate size... if so, allow it.
 496       //
 497       std::vector<Value*> Indices;
 498       const Type *ElTy = ConvertableToGEP(NewSrcTy, I->getOperand(1),
 499                                           Indices, &It);
 500       if (ElTy) {
 501         assert(ElTy == PVTy && "Internal error, setup wrong!");
 502         Res = new GetElementPtrInst(Constant::getNullValue(NewSrcTy),
 503                                     Indices, Name);
 504         VMC.ExprMap[I] = Res;
 505         Res->setOperand(0, ConvertExpressionToType(I->getOperand(0),
 506                                                    NewSrcTy, VMC));
 507       }
 508     }
 509
 510     // Otherwise, it could be that we have something like this:
 511     //     getelementptr [[sbyte] *] * %reg115, uint %reg138    ; [sbyte]**
 512     // and want to convert it into something like this:
 513     //     getelemenptr [[int] *] * %reg115, uint %reg138      ; [int]**
 514     //
 515     if (Res == 0) {
 516       const PointerType *NewSrcTy = PointerType::get(PVTy);
 517       Res = new GetElementPtrInst(Constant::getNullValue(NewSrcTy),
 518                                   GEP->copyIndices(), Name);
 519       VMC.ExprMap[I] = Res;
 520       Res->setOperand(0, ConvertExpressionToType(I->getOperand(0),
 521                                                  NewSrcTy, VMC));
 522     }
 523
 524
 525     assert(Res && "Didn't find match!");
 526     break;   // No match, maybe next time.
 527   }
 528
 529   default:
 530     assert(0 && "Expression convertable, but don't know how to convert?");
 531     return 0;
 532   }
 533
 534   assert(Res->getType() == Ty && "Didn't convert expr to correct type!");
 535
 536   BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 537   assert(It != BIL.end() && "Instruction not in own basic block??");
 538   BIL.insert(It, Res);
 539
 540   // Add the instruction to the expression map
 541   VMC.ExprMap[I] = Res;
 542
 543   // Expressions are only convertable if all of the users of the expression can
 544   // have this value converted.  This makes use of the map to avoid infinite
 545   // recursion.
 546   //
 547   unsigned NumUses = I->use_size();
 548   for (unsigned It = 0; It < NumUses; ) {
 549     unsigned OldSize = NumUses;
 550     ConvertOperandToType(*(I->use_begin()+It), I, Res, VMC);
 551     NumUses = I->use_size();
 552     if (NumUses == OldSize) ++It;
 553   }
 554
 555 #ifdef DEBUG_EXPR_CONVERT
 556   cerr << "ExpIn: " << (void*)I << " " << I
 557        << "ExpOut: " << (void*)Res << " " << Res;
 558 #endif
 559
 560   if (I->use_empty()) {
 561 #ifdef DEBUG_EXPR_CONVERT
 562     cerr << "EXPR DELETING: " << (void*)I << " " << I;
 563 #endif
 564     BIL.remove(I);
 565     VMC.OperandsMapped.erase(I);
 566     VMC.ExprMap.erase(I);
 567     delete I;
 568   }
 569
 570   return Res;
 571 }
 572
 573
 574
 575 // ValueConvertableToType - Return true if it is possible
 576 bool ValueConvertableToType(Value *V, const Type *Ty,
 577                              ValueTypeCache &ConvertedTypes) {
 578   ValueTypeCache::iterator I = ConvertedTypes.find(V);
 579   if (I != ConvertedTypes.end()) return I->second == Ty;
 580   ConvertedTypes[V] = Ty;
 581
 582   // It is safe to convert the specified value to the specified type IFF all of
 583   // the uses of the value can be converted to accept the new typed value.
 584   //
 585   if (V->getType() != Ty) {
 586     for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I)
 587       if (!OperandConvertableToType(*I, V, Ty, ConvertedTypes))
 588         return false;
 589   }
 590
 591   return true;
 592 }
 593
 594
 595
 596
 597
 598 // OperandConvertableToType - Return true if it is possible to convert operand
 599 // V of User (instruction) U to the specified type.  This is true iff it is
 600 // possible to change the specified instruction to accept this.  CTMap is a map
 601 // of converted types, so that circular definitions will see the future type of
 602 // the expression, not the static current type.
 603 //
 604 static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
 605                                      ValueTypeCache &CTMap) {
 606   //  if (V->getType() == Ty) return true;   // Operand already the right type?
 607
 608   // Expression type must be holdable in a register.
 609   if (!Ty->isFirstClassType())
 610     return false;
 611
 612   Instruction *I = dyn_cast<Instruction>(U);
 613   if (I == 0) return false;              // We can't convert!
 614
 615   switch (I->getOpcode()) {
 616   case Instruction::Cast:
 617     assert(I->getOperand(0) == V);
 618     // We can convert the expr if the cast destination type is losslessly
 619     // convertable to the requested type.
 620     // Also, do not change a cast that is a noop cast.  For all intents and
 621     // purposes it should be eliminated.
 622     if (!Ty->isLosslesslyConvertableTo(I->getOperand(0)->getType()) ||
 623         I->getType() == I->getOperand(0)->getType())
 624       return false;
 625
 626
 627 #if 1
 628     // We also do not allow conversion of a cast that casts from a ptr to array
 629     // of X to a *X.  For example: cast [4 x %List *] * %val to %List * *
 630     //
 631     if (PointerType *SPT = dyn_cast<PointerType>(I->getOperand(0)->getType()))
 632       if (PointerType *DPT = dyn_cast<PointerType>(I->getType()))
 633         if (ArrayType *AT = dyn_cast<ArrayType>(SPT->getElementType()))
 634           if (AT->getElementType() == DPT->getElementType())
 635             return false;
 636 #endif
 637     return true;
 638
 639   case Instruction::Add:
 640     if (isa<PointerType>(Ty)) {
 641       Value *IndexVal = I->getOperand(V == I->getOperand(0) ? 1 : 0);
 642       std::vector<Value*> Indices;
 643       if (const Type *ETy = ConvertableToGEP(Ty, IndexVal, Indices)) {
 644         const Type *RetTy = PointerType::get(ETy);
 645
 646         // Only successful if we can convert this type to the required type
 647         if (ValueConvertableToType(I, RetTy, CTMap)) {
 648           CTMap[I] = RetTy;
 649           return true;
 650         }
 651         // We have to return failure here because ValueConvertableToType could
 652         // have polluted our map
 653         return false;
 654       }
 655     }
 656     // FALLTHROUGH
 657   case Instruction::Sub: {
 658     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
 659     return ValueConvertableToType(I, Ty, CTMap) &&
 660            ExpressionConvertableToType(OtherOp, Ty, CTMap);
 661   }
 662   case Instruction::SetEQ:
 663   case Instruction::SetNE: {
 664     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
 665     return ExpressionConvertableToType(OtherOp, Ty, CTMap);
 666   }
 667   case Instruction::Shr:
 668     if (Ty->isSigned() != V->getType()->isSigned()) return false;
 669     // FALL THROUGH
 670   case Instruction::Shl:
 671     assert(I->getOperand(0) == V);
 672     return ValueConvertableToType(I, Ty, CTMap);
 673
 674   case Instruction::Free:
 675     assert(I->getOperand(0) == V);
 676     return isa<PointerType>(Ty);    // Free can free any pointer type!
 677
 678   case Instruction::Load:
 679     // Cannot convert the types of any subscripts...
 680     if (I->getOperand(0) != V) return false;
 681
 682     if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
 683       LoadInst *LI = cast<LoadInst>(I);
 684
 685       if (LI->hasIndices() && !AllIndicesZero(LI))
 686         return false;
 687
 688       const Type *LoadedTy = PT->getElementType();
 689
 690       // They could be loading the first element of a composite type...
 691       if (const CompositeType *CT = dyn_cast<CompositeType>(LoadedTy)) {
 692         unsigned Offset = 0;     // No offset, get first leaf.
 693         std::vector<Value*> Indices;  // Discarded...
 694         LoadedTy = getStructOffsetType(CT, Offset, Indices, false);
 695         assert(Offset == 0 && "Offset changed from zero???");
 696       }
 697
 698       if (!LoadedTy->isFirstClassType())
 699         return false;
 700
 701       if (TD.getTypeSize(LoadedTy) != TD.getTypeSize(LI->getType()))
 702         return false;
 703
 704       return ValueConvertableToType(LI, LoadedTy, CTMap);
 705     }
 706     return false;
 707
 708   case Instruction::Store: {
 709     StoreInst *SI = cast<StoreInst>(I);
 710     if (SI->hasIndices()) return false;
 711
 712     if (V == I->getOperand(0)) {
 713       ValueTypeCache::iterator CTMI = CTMap.find(I->getOperand(1));
 714       if (CTMI != CTMap.end()) {   // Operand #1 is in the table already?
 715         // If so, check to see if it's Ty*, or, more importantly, if it is a
 716         // pointer to a structure where the first element is a Ty... this code
 717         // is neccesary because we might be trying to change the source and
 718         // destination type of the store (they might be related) and the dest
 719         // pointer type might be a pointer to structure.  Below we allow pointer
 720         // to structures where the 0th element is compatible with the value,
 721         // now we have to support the symmetrical part of this.
 722         //
 723         const Type *ElTy = cast<PointerType>(CTMI->second)->getElementType();
 724
 725         // Already a pointer to what we want?  Trivially accept...
 726         if (ElTy == Ty) return true;
 727
 728         // Tricky case now, if the destination is a pointer to structure,
 729         // obviously the source is not allowed to be a structure (cannot copy
 730         // a whole structure at a time), so the level raiser must be trying to
 731         // store into the first field.  Check for this and allow it now:
 732         //
 733         if (StructType *SElTy = dyn_cast<StructType>(ElTy)) {
 734           unsigned Offset = 0;
 735           std::vector<Value*> Indices;
 736           ElTy = getStructOffsetType(ElTy, Offset, Indices, false);
 737           assert(Offset == 0 && "Offset changed!");
 738           if (ElTy == 0)    // Element at offset zero in struct doesn't exist!
 739             return false;   // Can only happen for {}*
 740
 741           if (ElTy == Ty)   // Looks like the 0th element of structure is
 742             return true;    // compatible!  Accept now!
 743
 744           // Otherwise we know that we can't work, so just stop trying now.
 745           return false;
 746         }
 747       }
 748
 749       // Can convert the store if we can convert the pointer operand to match
 750       // the new  value type...
 751       return ExpressionConvertableToType(I->getOperand(1), PointerType::get(Ty),
 752                                          CTMap);
 753     } else if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
 754       const Type *ElTy = PT->getElementType();
 755       assert(V == I->getOperand(1));
 756
 757       if (isa<StructType>(ElTy)) {
 758         // We can change the destination pointer if we can store our first
 759         // argument into the first element of the structure...
 760         //
 761         unsigned Offset = 0;
 762         std::vector<Value*> Indices;
 763         ElTy = getStructOffsetType(ElTy, Offset, Indices, false);
 764         assert(Offset == 0 && "Offset changed!");
 765         if (ElTy == 0)    // Element at offset zero in struct doesn't exist!
 766           return false;   // Can only happen for {}*
 767       }
 768
 769       // Must move the same amount of data...
 770       if (TD.getTypeSize(ElTy) != TD.getTypeSize(I->getOperand(0)->getType()))
 771         return false;
 772
 773       // Can convert store if the incoming value is convertable...
 774       return ExpressionConvertableToType(I->getOperand(0), ElTy, CTMap);
 775     }
 776     return false;
 777   }
 778
 779   case Instruction::GetElementPtr:
 780     if (V != I->getOperand(0) || !isa<PointerType>(Ty)) return false;
 781
 782     // If we have a two operand form of getelementptr, this is really little
 783     // more than a simple addition.  As with addition, check to see if the
 784     // getelementptr instruction can be changed to index into the new type.
 785     //
 786     if (I->getNumOperands() == 2) {
 787       const Type *OldElTy = cast<PointerType>(I->getType())->getElementType();
 788       unsigned DataSize = TD.getTypeSize(OldElTy);
 789       Value *Index = I->getOperand(1);
 790       Instruction *TempScale = 0;
 791
 792       // If the old data element is not unit sized, we have to create a scale
 793       // instruction so that ConvertableToGEP will know the REAL amount we are
 794       // indexing by.  Note that this is never inserted into the instruction
 795       // stream, so we have to delete it when we're done.
 796       //
 797       if (DataSize != 1) {
 798         TempScale = BinaryOperator::create(Instruction::Mul, Index,
 799                                            ConstantUInt::get(Type::UIntTy,
 800                                                              DataSize));
 801         Index = TempScale;
 802       }
 803
 804       // Check to see if the second argument is an expression that can
 805       // be converted to the appropriate size... if so, allow it.
 806       //
 807       std::vector<Value*> Indices;
 808       const Type *ElTy = ConvertableToGEP(Ty, Index, Indices);
 809       delete TempScale;   // Free our temporary multiply if we made it
 810
 811       if (ElTy == 0) return false;  // Cannot make conversion...
 812       return ValueConvertableToType(I, PointerType::get(ElTy), CTMap);
 813     }
 814     return false;
 815
 816   case Instruction::PHINode: {
 817     PHINode *PN = cast<PHINode>(I);
 818     for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i)
 819       if (!ExpressionConvertableToType(PN->getIncomingValue(i), Ty, CTMap))
 820         return false;
 821     return ValueConvertableToType(PN, Ty, CTMap);
 822   }
 823
 824   case Instruction::Call: {
 825     User::op_iterator OI = find(I->op_begin(), I->op_end(), V);
 826     assert (OI != I->op_end() && "Not using value!");
 827     unsigned OpNum = OI - I->op_begin();
 828
 829     // Are we trying to change the function pointer value to a new type?
 830     if (OpNum == 0) {
 831       PointerType *PTy = dyn_cast<PointerType>(Ty);
 832       if (PTy == 0) return false;  // Can't convert to a non-pointer type...
 833       FunctionType *MTy = dyn_cast<FunctionType>(PTy->getElementType());
 834       if (MTy == 0) return false;  // Can't convert to a non ptr to function...
 835
 836       // Perform sanity checks to make sure that new function type has the
 837       // correct number of arguments...
 838       //
 839       unsigned NumArgs = I->getNumOperands()-1;  // Don't include function ptr
 840
 841       // Cannot convert to a type that requires more fixed arguments than
 842       // the call provides...
 843       //
 844       if (NumArgs < MTy->getParamTypes().size()) return false;
 845
 846       // Unless this is a vararg function type, we cannot provide more arguments
 847       // than are desired...
 848       //
 849       if (!MTy->isVarArg() && NumArgs > MTy->getParamTypes().size())
 850         return false;
 851
 852       // Okay, at this point, we know that the call and the function type match
 853       // number of arguments.  Now we see if we can convert the arguments
 854       // themselves.  Note that we do not require operands to be convertable,
 855       // we can insert casts if they are convertible but not compatible.  The
 856       // reason for this is that we prefer to have resolved functions but casted
 857       // arguments if possible.
 858       //
 859       const FunctionType::ParamTypes &PTs = MTy->getParamTypes();
 860       for (unsigned i = 0, NA = PTs.size(); i < NA; ++i)
 861         if (!PTs[i]->isLosslesslyConvertableTo(I->getOperand(i+1)->getType()))
 862           return false;   // Operands must have compatible types!
 863
 864       // Okay, at this point, we know that all of the arguments can be
 865       // converted.  We succeed if we can change the return type if
 866       // neccesary...
 867       //
 868       return ValueConvertableToType(I, MTy->getReturnType(), CTMap);
 869     }
 870
 871     const PointerType *MPtr = cast<PointerType>(I->getOperand(0)->getType());
 872     const FunctionType *MTy = cast<FunctionType>(MPtr->getElementType());
 873     if (!MTy->isVarArg()) return false;
 874
 875     if ((OpNum-1) < MTy->getParamTypes().size())
 876       return false;  // It's not in the varargs section...
 877
 878     // If we get this far, we know the value is in the varargs section of the
 879     // function!  We can convert if we don't reinterpret the value...
 880     //
 881     return Ty->isLosslesslyConvertableTo(V->getType());
 882   }
 883   }
 884   return false;
 885 }
 886
 887
 888 void ConvertValueToNewType(Value *V, Value *NewVal, ValueMapCache &VMC) {
 889   ValueHandle VH(VMC, V);
 890
 891   unsigned NumUses = V->use_size();
 892   for (unsigned It = 0; It < NumUses; ) {
 893     unsigned OldSize = NumUses;
 894     ConvertOperandToType(*(V->use_begin()+It), V, NewVal, VMC);
 895     NumUses = V->use_size();
 896     if (NumUses == OldSize) ++It;
 897   }
 898 }
 899
 900
 901
 902 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
 903                                  ValueMapCache &VMC) {
 904   if (isa<ValueHandle>(U)) return;  // Valuehandles don't let go of operands...
 905
 906   if (VMC.OperandsMapped.count(U)) return;
 907   VMC.OperandsMapped.insert(U);
 908
 909   ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(U);
 910   if (VMCI != VMC.ExprMap.end())
 911     return;
 912
 913
 914   Instruction *I = cast<Instruction>(U);  // Only Instructions convertable
 915
 916   BasicBlock *BB = I->getParent();
 917   BasicBlock::InstListType &BIL = BB->getInstList();
 918   std::string Name = I->getName();  if (!Name.empty()) I->setName("");
 919   Instruction *Res;     // Result of conversion
 920
 921   //cerr << endl << endl << "Type:\t" << Ty << "\nInst: " << I << "BB Before: " << BB << endl;
 922
 923   // Prevent I from being removed...
 924   ValueHandle IHandle(VMC, I);
 925
 926   const Type *NewTy = NewVal->getType();
 927   Constant *Dummy = (NewTy != Type::VoidTy) ?
 928                   Constant::getNullValue(NewTy) : 0;
 929
 930   switch (I->getOpcode()) {
 931   case Instruction::Cast:
 932     assert(I->getOperand(0) == OldVal);
 933     Res = new CastInst(NewVal, I->getType(), Name);
 934     break;
 935
 936   case Instruction::Add:
 937     if (isa<PointerType>(NewTy)) {
 938       Value *IndexVal = I->getOperand(OldVal == I->getOperand(0) ? 1 : 0);
 939       std::vector<Value*> Indices;
 940       BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 941
 942       if (const Type *ETy = ConvertableToGEP(NewTy, IndexVal, Indices, &It)) {
 943         // If successful, convert the add to a GEP
 944         //const Type *RetTy = PointerType::get(ETy);
 945         // First operand is actually the given pointer...
 946         Res = new GetElementPtrInst(NewVal, Indices, Name);
 947         assert(cast<PointerType>(Res->getType())->getElementType() == ETy &&
 948                "ConvertableToGEP broken!");
 949         break;
 950       }
 951     }
 952     // FALLTHROUGH
 953
 954   case Instruction::Sub:
 955   case Instruction::SetEQ:
 956   case Instruction::SetNE: {
 957     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
 958                                  Dummy, Dummy, Name);
 959     VMC.ExprMap[I] = Res;   // Add node to expression eagerly
 960
 961     unsigned OtherIdx = (OldVal == I->getOperand(0)) ? 1 : 0;
 962     Value *OtherOp    = I->getOperand(OtherIdx);
 963     Value *NewOther   = ConvertExpressionToType(OtherOp, NewTy, VMC);
 964
 965     Res->setOperand(OtherIdx, NewOther);
 966     Res->setOperand(!OtherIdx, NewVal);
 967     break;
 968   }
 969   case Instruction::Shl:
 970   case Instruction::Shr:
 971     assert(I->getOperand(0) == OldVal);
 972     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), NewVal,
 973                         I->getOperand(1), Name);
 974     break;
 975
 976   case Instruction::Free:            // Free can free any pointer type!
 977     assert(I->getOperand(0) == OldVal);
 978     Res = new FreeInst(NewVal);
 979     break;
 980
 981
 982   case Instruction::Load: {
 983     assert(I->getOperand(0) == OldVal && isa<PointerType>(NewVal->getType()));
 984     const Type *LoadedTy =
 985       cast<PointerType>(NewVal->getType())->getElementType();
 986
 987     std::vector<Value*> Indices;
 988     Indices.push_back(ConstantUInt::get(Type::UIntTy, 0));
 989
 990     if (const CompositeType *CT = dyn_cast<CompositeType>(LoadedTy)) {
 991       unsigned Offset = 0;   // No offset, get first leaf.
 992       LoadedTy = getStructOffsetType(CT, Offset, Indices, false);
 993     }
 994     assert(LoadedTy->isFirstClassType());
 995
 996     Res = new LoadInst(NewVal, Indices, Name);
 997     assert(Res->getType()->isFirstClassType() && "Load of structure or array!");
 998     break;
 999   }
1000
1001   case Instruction::Store: {
1002     if (I->getOperand(0) == OldVal) {  // Replace the source value
1003       const PointerType *NewPT = PointerType::get(NewTy);
1004       Res = new StoreInst(NewVal, Constant::getNullValue(NewPT));
1005       VMC.ExprMap[I] = Res;
1006       Res->setOperand(1, ConvertExpressionToType(I->getOperand(1), NewPT, VMC));
1007     } else {                           // Replace the source pointer
1008       const Type *ValTy = cast<PointerType>(NewTy)->getElementType();
1009       std::vector<Value*> Indices;
1010
1011       if (isa<StructType>(ValTy)) {
1012         unsigned Offset = 0;
1013         Indices.push_back(ConstantUInt::get(Type::UIntTy, 0));
1014         ValTy = getStructOffsetType(ValTy, Offset, Indices, false);
1015         assert(Offset == 0 && ValTy);
1016       }
1017
1018       Res = new StoreInst(Constant::getNullValue(ValTy), NewVal, Indices);
1019       VMC.ExprMap[I] = Res;
1020       Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), ValTy, VMC));
1021     }
1022     break;
1023   }
1024
1025
1026   case Instruction::GetElementPtr: {
1027     // Convert a one index getelementptr into just about anything that is
1028     // desired.
1029     //
1030     BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
1031     const Type *OldElTy = cast<PointerType>(I->getType())->getElementType();
1032     unsigned DataSize = TD.getTypeSize(OldElTy);
1033     Value *Index = I->getOperand(1);
1034
1035     if (DataSize != 1) {
1036       // Insert a multiply of the old element type is not a unit size...
1037       Index = BinaryOperator::create(Instruction::Mul, Index,
1038                                      ConstantUInt::get(Type::UIntTy, DataSize));
1039       It = BIL.insert(It, cast<Instruction>(Index))+1;
1040     }
1041
1042     // Perform the conversion now...
1043     //
1044     std::vector<Value*> Indices;
1045     const Type *ElTy = ConvertableToGEP(NewVal->getType(), Index, Indices, &It);
1046     assert(ElTy != 0 && "GEP Conversion Failure!");
1047     Res = new GetElementPtrInst(NewVal, Indices, Name);
1048     assert(Res->getType() == PointerType::get(ElTy) &&
1049            "ConvertableToGet failed!");
1050   }
1051 #if 0
1052     if (I->getType() == PointerType::get(Type::SByteTy)) {
1053       // Convert a getelementptr sbyte * %reg111, uint 16 freely back to
1054       // anything that is a pointer type...
1055       //
1056       BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
1057
1058       // Check to see if the second argument is an expression that can
1059       // be converted to the appropriate size... if so, allow it.
1060       //
1061       std::vector<Value*> Indices;
1062       const Type *ElTy = ConvertableToGEP(NewVal->getType(), I->getOperand(1),
1063                                           Indices, &It);
1064       assert(ElTy != 0 && "GEP Conversion Failure!");
1065
1066       Res = new GetElementPtrInst(NewVal, Indices, Name);
1067     } else {
1068       // Convert a getelementptr ulong * %reg123, uint %N
1069       // to        getelementptr  long * %reg123, uint %N
1070       // ... where the type must simply stay the same size...
1071       //
1072       Res = new GetElementPtrInst(NewVal,
1073                                   cast<GetElementPtrInst>(I)->copyIndices(),
1074                                   Name);
1075     }
1076 #endif
1077     break;
1078
1079   case Instruction::PHINode: {
1080     PHINode *OldPN = cast<PHINode>(I);
1081     PHINode *NewPN = new PHINode(NewTy, Name);
1082     VMC.ExprMap[I] = NewPN;
1083
1084     while (OldPN->getNumOperands()) {
1085       BasicBlock *BB = OldPN->getIncomingBlock(0);
1086       Value *OldVal = OldPN->getIncomingValue(0);
1087       OldPN->removeIncomingValue(BB);
1088       Value *V = ConvertExpressionToType(OldVal, NewTy, VMC);
1089       NewPN->addIncoming(V, BB);
1090     }
1091     Res = NewPN;
1092     break;
1093   }
1094
1095   case Instruction::Call: {
1096     Value *Meth = I->getOperand(0);
1097     std::vector<Value*> Params(I->op_begin()+1, I->op_end());
1098
1099     if (Meth == OldVal) {   // Changing the function pointer?
1100       PointerType *NewPTy = cast<PointerType>(NewVal->getType());
1101       FunctionType *NewTy = cast<FunctionType>(NewPTy->getElementType());
1102       const FunctionType::ParamTypes &PTs = NewTy->getParamTypes();
1103
1104       // Get an iterator to the call instruction so that we can insert casts for
1105       // operands if needbe.  Note that we do not require operands to be
1106       // convertable, we can insert casts if they are convertible but not
1107       // compatible.  The reason for this is that we prefer to have resolved
1108       // functions but casted arguments if possible.
1109       //
1110       BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
1111
1112       // Convert over all of the call operands to their new types... but only
1113       // convert over the part that is not in the vararg section of the call.
1114       //
1115       for (unsigned i = 0; i < PTs.size(); ++i)
1116         if (Params[i]->getType() != PTs[i]) {
1117           // Create a cast to convert it to the right type, we know that this
1118           // is a lossless cast...
1119           //
1120           Params[i] = new CastInst(Params[i], PTs[i], "call.resolve.cast");
1121           It = BIL.insert(It, cast<Instruction>(Params[i]))+1;
1122         }
1123       Meth = NewVal;  // Update call destination to new value
1124
1125     } else {                   // Changing an argument, must be in vararg area
1126       std::vector<Value*>::iterator OI =
1127         find(Params.begin(), Params.end(), OldVal);
1128       assert (OI != Params.end() && "Not using value!");
1129
1130       *OI = NewVal;
1131     }
1132
1133     Res = new CallInst(Meth, Params, Name);
1134     break;
1135   }
1136   default:
1137     assert(0 && "Expression convertable, but don't know how to convert?");
1138     return;
1139   }
1140
1141   // If the instruction was newly created, insert it into the instruction
1142   // stream.
1143   //
1144   BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
1145   assert(It != BIL.end() && "Instruction not in own basic block??");
1146   BIL.insert(It, Res);   // Keep It pointing to old instruction
1147
1148 #ifdef DEBUG_EXPR_CONVERT
1149   cerr << "COT CREATED: "  << (void*)Res << " " << Res;
1150   cerr << "In: " << (void*)I << " " << I << "Out: " << (void*)Res << " " << Res;
1151 #endif
1152
1153   // Add the instruction to the expression map
1154   VMC.ExprMap[I] = Res;
1155
1156   if (I->getType() != Res->getType())
1157     ConvertValueToNewType(I, Res, VMC);
1158   else {
1159     for (unsigned It = 0; It < I->use_size(); ) {
1160       User *Use = *(I->use_begin()+It);
1161       if (isa<ValueHandle>(Use))            // Don't remove ValueHandles!
1162         ++It;
1163       else
1164         Use->replaceUsesOfWith(I, Res);
1165     }
1166
1167     if (I->use_empty()) {
1168       // Now we just need to remove the old instruction so we don't get infinite
1169       // loops.  Note that we cannot use DCE because DCE won't remove a store
1170       // instruction, for example.
1171       //
1172 #ifdef DEBUG_EXPR_CONVERT
1173       cerr << "DELETING: " << (void*)I << " " << I;
1174 #endif
1175       BIL.remove(I);
1176       VMC.OperandsMapped.erase(I);
1177       VMC.ExprMap.erase(I);
1178       delete I;
1179     } else {
1180       for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
1181            UI != UE; ++UI)
1182         assert(isa<ValueHandle>((Value*)*UI) &&"Uses of Instruction remain!!!");
1183     }
1184   }
1185 }
1186
1187
1188 ValueHandle::ValueHandle(ValueMapCache &VMC, Value *V)
1189   : Instruction(Type::VoidTy, UserOp1, ""), Cache(VMC) {
1190 #ifdef DEBUG_EXPR_CONVERT
1191   //cerr << "VH AQUIRING: " << (void*)V << " " << V;
1192 #endif
1193   Operands.push_back(Use(V, this));
1194 }
1195
1196 static void RecursiveDelete(ValueMapCache &Cache, Instruction *I) {
1197   if (!I || !I->use_empty()) return;
1198
1199   assert(I->getParent() && "Inst not in basic block!");
1200
1201 #ifdef DEBUG_EXPR_CONVERT
1202   //cerr << "VH DELETING: " << (void*)I << " " << I;
1203 #endif
1204
1205   for (User::op_iterator OI = I->op_begin(), OE = I->op_end();
1206        OI != OE; ++OI)
1207     if (Instruction *U = dyn_cast<Instruction>(*OI)) {
1208       *OI = 0;
1209       RecursiveDelete(Cache, U);
1210     }
1211
1212   I->getParent()->getInstList().remove(I);
1213
1214   Cache.OperandsMapped.erase(I);
1215   Cache.ExprMap.erase(I);
1216   delete I;
1217 }
1218
1219 ValueHandle::~ValueHandle() {
1220   if (Operands[0]->use_size() == 1) {
1221     Value *V = Operands[0];
1222     Operands[0] = 0;   // Drop use!
1223
1224     // Now we just need to remove the old instruction so we don't get infinite
1225     // loops.  Note that we cannot use DCE because DCE won't remove a store
1226     // instruction, for example.
1227     //
1228     RecursiveDelete(Cache, dyn_cast<Instruction>(V));
1229   } else {
1230 #ifdef DEBUG_EXPR_CONVERT
1231     //cerr << "VH RELEASING: " << (void*)Operands[0].get() << " " << Operands[0]->use_size() << " " << Operands[0];
1232 #endif
1233   }
1234 }