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