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/Method.h"
  11 #include "llvm/Support/STLExtras.h"
  12 #include "llvm/iOther.h"
  13 #include "llvm/iMemory.h"
  14 #include "llvm/ConstPoolVals.h"
  15 #include "llvm/Optimizations/ConstantHandling.h"
  16 #include "llvm/Optimizations/DCE.h"
  17 #include <map>
  18 #include <algorithm>
  19
  20 #include "llvm/Assembly/Writer.h"
  21
  22 //#define DEBUG_EXPR_CONVERT 1
  23
  24 static inline const Type *getTy(const Value *V, ValueTypeCache &CT) {
  25   ValueTypeCache::iterator I = CT.find(V);
  26   if (I == CT.end()) return V->getType();
  27   return I->second;
  28 }
  29
  30 GetElementPtrInst *getAddToGEPResult(const Type *Ty, const Value *V) {
  31   const StructType *StructTy = getPointedToStruct(Ty);
  32   if (StructTy == 0) return 0;    // Must be a pointer to a struct...
  33
  34   // Must be a constant unsigned offset value... get it now...
  35   if (!isa<ConstPoolUInt>(V)) return 0;
  36   unsigned Offset = cast<ConstPoolUInt>(V)->getValue();
  37
  38   // Check to make sure the offset is somewhat legitiment w.r.t the struct
  39   // type...
  40   if (Offset >= TD.getTypeSize(StructTy)) return 0;
  41
  42   // If we get this far, we have succeeded... TODO: We need to handle array
  43   // indexing as well...
  44   const StructLayout *SL = TD.getStructLayout(StructTy);
  45   vector<ConstPoolVal*> Offsets;
  46   unsigned ActualOffset = Offset;
  47   const Type *ElTy = getStructOffsetType(StructTy, ActualOffset, Offsets);
  48
  49   if (ActualOffset != Offset) return 0;  // TODO: Handle Array indexing...
  50
  51   // Success!  Return the GEP instruction, with a dummy first argument.
  52   ConstPoolVal *Dummy = ConstPoolVal::getNullConstant(Ty);
  53   return new GetElementPtrInst(Dummy, Offsets);
  54 }
  55
  56
  57
  58 static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
  59                                      ValueTypeCache &ConvertedTypes);
  60
  61 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
  62                                  ValueMapCache &VMC);
  63
  64
  65 // ExpressionConvertableToType - Return true if it is possible
  66 bool ExpressionConvertableToType(Value *V, const Type *Ty,
  67                                  ValueTypeCache &CTMap) {
  68   // Expression type must be holdable in a register.
  69   if (!isFirstClassType(Ty))
  70     return false;
  71
  72   ValueTypeCache::iterator CTMI = CTMap.find(V);
  73   if (CTMI != CTMap.end()) return CTMI->second == Ty;
  74   CTMap[V] = Ty;
  75
  76   // Expressions are only convertable if all of the users of the expression can
  77   // have this value converted.  This makes use of the map to avoid infinite
  78   // recursion.
  79   //
  80   for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I)
  81     if (!OperandConvertableToType(*I, V, Ty, CTMap))
  82       return false;
  83
  84   Instruction *I = dyn_cast<Instruction>(V);
  85   if (I == 0) {
  86     // It's not an instruction, check to see if it's a constant... all constants
  87     // can be converted to an equivalent value (except pointers, they can't be
  88     // const prop'd in general).  We just ask the constant propogator to see if
  89     // it can convert the value...
  90     //
  91     if (ConstPoolVal *CPV = dyn_cast<ConstPoolVal>(V))
  92       if (opt::ConstantFoldCastInstruction(CPV, Ty))
  93         return true;  // Don't worry about deallocating, it's a constant.
  94
  95     return false;              // Otherwise, we can't convert!
  96   }
  97   if (I->getType() == Ty) return false;  // Expression already correct type!
  98
  99   switch (I->getOpcode()) {
 100   case Instruction::Cast:
 101     // We can convert the expr if the cast destination type is losslessly
 102     // convertable to the requested type.
 103     return losslessCastableTypes(Ty, I->getType());
 104
 105   case Instruction::Add:
 106   case Instruction::Sub:
 107     return ExpressionConvertableToType(I->getOperand(0), Ty, CTMap) &&
 108            ExpressionConvertableToType(I->getOperand(1), Ty, CTMap);
 109   case Instruction::Shr:
 110     if (Ty->isSigned() != V->getType()->isSigned()) return false;
 111     // FALL THROUGH
 112   case Instruction::Shl:
 113     return ExpressionConvertableToType(I->getOperand(0), Ty, CTMap);
 114
 115   case Instruction::Load: {
 116     LoadInst *LI = cast<LoadInst>(I);
 117     if (LI->hasIndices()) return false;
 118
 119     return ExpressionConvertableToType(LI->getPtrOperand(),
 120                                        PointerType::get(Ty), CTMap);
 121   }
 122   case Instruction::PHINode: {
 123     PHINode *PN = cast<PHINode>(I);
 124     for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i)
 125       if (!ExpressionConvertableToType(PN->getIncomingValue(i), Ty, CTMap))
 126         return false;
 127     return true;
 128   }
 129
 130   case Instruction::GetElementPtr: {
 131     // GetElementPtr's are directly convertable to a pointer type if they have
 132     // a number of zeros at the end.  Because removing these values does not
 133     // change the logical offset of the GEP, it is okay and fair to remove them.
 134     // This can change this:
 135     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 136     //   %t2 = cast %List * * %t1 to %List *
 137     // into
 138     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 139     //
 140     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 141     const PointerType *PTy = dyn_cast<PointerType>(Ty);
 142     if (!PTy) return false;
 143
 144     // Check to see if there are zero elements that we can remove from the
 145     // index array.  If there are, check to see if removing them causes us to
 146     // get to the right type...
 147     //
 148     vector<ConstPoolVal*> Indices = GEP->getIndices();
 149     const Type *BaseType = GEP->getPtrOperand()->getType();
 150
 151     while (Indices.size() &&
 152            cast<ConstPoolUInt>(Indices.back())->getValue() == 0) {
 153       Indices.pop_back();
 154       const Type *ElTy = GetElementPtrInst::getIndexedType(BaseType, Indices,
 155                                                            true);
 156       if (ElTy == PTy->getValueType())
 157         return true;  // Found a match!!
 158     }
 159     break;   // No match, maybe next time.
 160   }
 161   }
 162   return false;
 163 }
 164
 165
 166
 167
 168 Value *ConvertExpressionToType(Value *V, const Type *Ty, ValueMapCache &VMC) {
 169   ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(V);
 170   if (VMCI != VMC.ExprMap.end())
 171     return VMCI->second;
 172
 173 #ifdef DEBUG_EXPR_CONVERT
 174   cerr << "CETT: " << (void*)V << " " << V;
 175 #endif
 176
 177   Instruction *I = dyn_cast<Instruction>(V);
 178   if (I == 0)
 179     if (ConstPoolVal *CPV = cast<ConstPoolVal>(V)) {
 180       // Constants are converted by constant folding the cast that is required.
 181       // We assume here that all casts are implemented for constant prop.
 182       Value *Result = opt::ConstantFoldCastInstruction(CPV, Ty);
 183       assert(Result && "ConstantFoldCastInstruction Failed!!!");
 184
 185       // Add the instruction to the expression map
 186       VMC.ExprMap[V] = Result;
 187       return Result;
 188     }
 189
 190
 191   BasicBlock *BB = I->getParent();
 192   BasicBlock::InstListType &BIL = BB->getInstList();
 193   string Name = I->getName();  if (!Name.empty()) I->setName("");
 194   Instruction *Res;     // Result of conversion
 195
 196   ValueHandle IHandle(I);  // Prevent I from being removed!
 197
 198   ConstPoolVal *Dummy = ConstPoolVal::getNullConstant(Ty);
 199
 200   //cerr << endl << endl << "Type:\t" << Ty << "\nInst: " << I << "BB Before: " << BB << endl;
 201
 202   switch (I->getOpcode()) {
 203   case Instruction::Cast:
 204     Res = new CastInst(I->getOperand(0), Ty, Name);
 205     break;
 206
 207   case Instruction::Add:
 208   case Instruction::Sub:
 209     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
 210                                  Dummy, Dummy, Name);
 211     VMC.ExprMap[I] = Res;   // Add node to expression eagerly
 212
 213     Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC));
 214     Res->setOperand(1, ConvertExpressionToType(I->getOperand(1), Ty, VMC));
 215     break;
 216
 217   case Instruction::Shl:
 218   case Instruction::Shr:
 219     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), Dummy,
 220                         I->getOperand(1), Name);
 221     VMC.ExprMap[I] = Res;
 222     Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC));
 223     break;
 224
 225   case Instruction::Load: {
 226     LoadInst *LI = cast<LoadInst>(I);
 227     assert(!LI->hasIndices());
 228     Res = new LoadInst(ConstPoolVal::getNullConstant(PointerType::get(Ty)),
 229                        Name);
 230     VMC.ExprMap[I] = Res;
 231     Res->setOperand(0, ConvertExpressionToType(LI->getPtrOperand(),
 232                                                PointerType::get(Ty), VMC));
 233     break;
 234   }
 235
 236   case Instruction::PHINode: {
 237     PHINode *OldPN = cast<PHINode>(I);
 238     PHINode *NewPN = new PHINode(Ty, Name);
 239
 240     VMC.ExprMap[I] = NewPN;   // Add node to expression eagerly
 241     while (OldPN->getNumOperands()) {
 242       BasicBlock *BB = OldPN->getIncomingBlock(0);
 243       Value *OldVal = OldPN->getIncomingValue(0);
 244       ValueHandle OldValHandle(OldVal);
 245       OldPN->removeIncomingValue(BB);
 246       Value *V = ConvertExpressionToType(OldVal, Ty, VMC);
 247       NewPN->addIncoming(V, BB);
 248     }
 249     Res = NewPN;
 250     break;
 251   }
 252
 253   case Instruction::GetElementPtr: {
 254     // GetElementPtr's are directly convertable to a pointer type if they have
 255     // a number of zeros at the end.  Because removing these values does not
 256     // change the logical offset of the GEP, it is okay and fair to remove them.
 257     // This can change this:
 258     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 259     //   %t2 = cast %List * * %t1 to %List *
 260     // into
 261     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 262     //
 263     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 264
 265     // Check to see if there are zero elements that we can remove from the
 266     // index array.  If there are, check to see if removing them causes us to
 267     // get to the right type...
 268     //
 269     vector<ConstPoolVal*> Indices = GEP->getIndices();
 270     const Type *BaseType = GEP->getPtrOperand()->getType();
 271     const Type *PVTy = cast<PointerType>(Ty)->getValueType();
 272     Res = 0;
 273     while (Indices.size() &&
 274            cast<ConstPoolUInt>(Indices.back())->getValue() == 0) {
 275       Indices.pop_back();
 276       if (GetElementPtrInst::getIndexedType(BaseType, Indices, true) == PVTy) {
 277         if (Indices.size() == 0) {
 278           Res = new CastInst(GEP->getPtrOperand(), BaseType); // NOOP
 279         } else {
 280           Res = new GetElementPtrInst(GEP->getPtrOperand(), Indices, Name);
 281         }
 282         break;
 283       }
 284     }
 285     assert(Res && "Didn't find match!");
 286     break;   // No match, maybe next time.
 287   }
 288
 289   default:
 290     assert(0 && "Expression convertable, but don't know how to convert?");
 291     return 0;
 292   }
 293
 294   BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 295   assert(It != BIL.end() && "Instruction not in own basic block??");
 296   BIL.insert(It, Res);
 297
 298   // Add the instruction to the expression map
 299   VMC.ExprMap[I] = Res;
 300
 301   // Expressions are only convertable if all of the users of the expression can
 302   // have this value converted.  This makes use of the map to avoid infinite
 303   // recursion.
 304   //
 305   unsigned NumUses = I->use_size();
 306   for (unsigned It = 0; It < NumUses; ) {
 307     unsigned OldSize = NumUses;
 308     ConvertOperandToType(*(I->use_begin()+It), I, Res, VMC);
 309     NumUses = I->use_size();
 310     if (NumUses == OldSize) ++It;
 311   }
 312
 313 #ifdef DEBUG_EXPR_CONVERT
 314   cerr << "ExpIn: " << (void*)I << " " << I
 315        << "ExpOut: " << (void*)Res << " " << Res;
 316   cerr << "ExpCREATED: " << (void*)Res << " " << Res;
 317 #endif
 318
 319   if (I->use_empty()) {
 320 #ifdef DEBUG_EXPR_CONVERT
 321     cerr << "EXPR DELETING: " << (void*)I << " " << I;
 322 #endif
 323     BIL.remove(I);
 324     delete I;
 325   }
 326
 327   return Res;
 328 }
 329
 330
 331
 332 // RetValConvertableToType - Return true if it is possible
 333 bool RetValConvertableToType(Value *V, const Type *Ty,
 334                              ValueTypeCache &ConvertedTypes) {
 335   ValueTypeCache::iterator I = ConvertedTypes.find(V);
 336   if (I != ConvertedTypes.end()) return I->second == Ty;
 337   ConvertedTypes[V] = Ty;
 338
 339   // It is safe to convert the specified value to the specified type IFF all of
 340   // the uses of the value can be converted to accept the new typed value.
 341   //
 342   for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I)
 343     if (!OperandConvertableToType(*I, V, Ty, ConvertedTypes))
 344       return false;
 345
 346   return true;
 347 }
 348
 349
 350
 351
 352
 353
 354
 355 // OperandConvertableToType - Return true if it is possible to convert operand
 356 // V of User (instruction) U to the specified type.  This is true iff it is
 357 // possible to change the specified instruction to accept this.  CTMap is a map
 358 // of converted types, so that circular definitions will see the future type of
 359 // the expression, not the static current type.
 360 //
 361 static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
 362                                      ValueTypeCache &CTMap) {
 363   if (V->getType() == Ty) return true;   // Already the right type?
 364
 365   // Expression type must be holdable in a register.
 366   if (!isFirstClassType(Ty))
 367     return false;
 368
 369   Instruction *I = dyn_cast<Instruction>(U);
 370   if (I == 0) return false;              // We can't convert!
 371
 372   switch (I->getOpcode()) {
 373   case Instruction::Cast:
 374     assert(I->getOperand(0) == V);
 375     // We can convert the expr if the cast destination type is losslessly
 376     // convertable to the requested type.
 377     return losslessCastableTypes(Ty, I->getOperand(0)->getType());
 378
 379   case Instruction::Add:
 380     if (V == I->getOperand(0) && isa<CastInst>(I->getOperand(1))) {
 381       Instruction *GEP =
 382         getAddToGEPResult(Ty, cast<CastInst>(I->getOperand(1))->getOperand(0));
 383       if (GEP) {  // If successful, this Add can be converted to a GEP.
 384         const Type *RetTy = GEP->getType();  // Get the new type...
 385         delete GEP;  // We don't want the actual instruction yet...
 386         // Only successful if we can convert this type to the required type
 387         return RetValConvertableToType(I, RetTy, CTMap);
 388       }
 389     }
 390     // FALLTHROUGH
 391   case Instruction::Sub: {
 392     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
 393     return RetValConvertableToType(I, Ty, CTMap) &&
 394            ExpressionConvertableToType(OtherOp, Ty, CTMap);
 395   }
 396   case Instruction::SetEQ:
 397   case Instruction::SetNE: {
 398     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
 399     return ExpressionConvertableToType(OtherOp, Ty, CTMap);
 400   }
 401   case Instruction::Shr:
 402     if (Ty->isSigned() != V->getType()->isSigned()) return false;
 403     // FALL THROUGH
 404   case Instruction::Shl:
 405     assert(I->getOperand(0) == V);
 406     return RetValConvertableToType(I, Ty, CTMap);
 407
 408   case Instruction::Load:
 409     assert(I->getOperand(0) == V);
 410     if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
 411       LoadInst *LI = cast<LoadInst>(I);
 412       const Type *PVTy = PT->getValueType();
 413
 414       if (LI->hasIndices() || isa<ArrayType>(PVTy))
 415         return false;
 416
 417       if (!isFirstClassType(PVTy)) {
 418         // They could be loading the first element of a structure type...
 419         if (const StructType *ST = dyn_cast<StructType>(PVTy)) {
 420           unsigned Offset = 0;   // No offset, get first leaf.
 421           vector<ConstPoolVal*> Offsets;  // Discarded...
 422           const Type *Ty = getStructOffsetType(ST, Offset, Offsets, false);
 423           assert(Offset == 0 && "Offset changed from zero???");
 424           if (!isFirstClassType(Ty)) return false;
 425
 426           // See if the leaf type is compatible with the old return type...
 427           if (TD.getTypeSize(Ty) != TD.getTypeSize(LI->getType()))
 428             return false;
 429
 430           return RetValConvertableToType(LI, Ty, CTMap);
 431         }
 432         return false;
 433       }
 434
 435       if (TD.getTypeSize(PVTy) != TD.getTypeSize(LI->getType()))
 436         return false;
 437
 438       return RetValConvertableToType(LI, PVTy, CTMap);
 439     }
 440     return false;
 441
 442   case Instruction::Store: {
 443     StoreInst *SI = cast<StoreInst>(I);
 444     if (SI->hasIndices()) return false;
 445
 446     if (V == I->getOperand(0)) {
 447       // Can convert the store if we can convert the pointer operand to match
 448       // the new  value type...
 449       return ExpressionConvertableToType(I->getOperand(1), PointerType::get(Ty),
 450                                          CTMap);
 451     } else if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
 452       if (isa<ArrayType>(PT->getValueType()))
 453         return false;  // Avoid getDataSize on unsized array type!
 454       assert(V == I->getOperand(1));
 455
 456       // Must move the same amount of data...
 457       if (TD.getTypeSize(PT->getValueType()) !=
 458           TD.getTypeSize(I->getOperand(0)->getType())) return false;
 459
 460       // Can convert store if the incoming value is convertable...
 461       return ExpressionConvertableToType(I->getOperand(0), PT->getValueType(),
 462                                          CTMap);
 463     }
 464     return false;
 465   }
 466
 467   case Instruction::PHINode: {
 468     PHINode *PN = cast<PHINode>(I);
 469     for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i)
 470       if (!ExpressionConvertableToType(PN->getIncomingValue(i), Ty, CTMap))
 471         return false;
 472     return RetValConvertableToType(PN, Ty, CTMap);
 473   }
 474
 475 #if 0
 476   case Instruction::GetElementPtr: {
 477     // GetElementPtr's are directly convertable to a pointer type if they have
 478     // a number of zeros at the end.  Because removing these values does not
 479     // change the logical offset of the GEP, it is okay and fair to remove them.
 480     // This can change this:
 481     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 482     //   %t2 = cast %List * * %t1 to %List *
 483     // into
 484     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 485     //
 486     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 487     const PointerType *PTy = dyn_cast<PointerType>(Ty);
 488     if (!PTy) return false;
 489
 490     // Check to see if there are zero elements that we can remove from the
 491     // index array.  If there are, check to see if removing them causes us to
 492     // get to the right type...
 493     //
 494     vector<ConstPoolVal*> Indices = GEP->getIndices();
 495     const Type *BaseType = GEP->getPtrOperand()->getType();
 496
 497     while (Indices.size() &&
 498            cast<ConstPoolUInt>(Indices.back())->getValue() == 0) {
 499       Indices.pop_back();
 500       const Type *ElTy = GetElementPtrInst::getIndexedType(BaseType, Indices,
 501                                                            true);
 502       if (ElTy == PTy->getValueType())
 503         return true;  // Found a match!!
 504     }
 505     break;   // No match, maybe next time.
 506   }
 507 #endif
 508   }
 509   return false;
 510 }
 511
 512
 513 void ConvertUsersType(Value *V, Value *NewVal, ValueMapCache &VMC) {
 514   ValueHandle VH(V);
 515
 516   unsigned NumUses = V->use_size();
 517   for (unsigned It = 0; It < NumUses; ) {
 518     unsigned OldSize = NumUses;
 519     ConvertOperandToType(*(V->use_begin()+It), V, NewVal, VMC);
 520     NumUses = V->use_size();
 521     if (NumUses == OldSize) ++It;
 522   }
 523 }
 524
 525
 526
 527 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
 528                                  ValueMapCache &VMC) {
 529   if (isa<ValueHandle>(U)) return;  // Valuehandles don't let go of operands...
 530
 531   if (VMC.OperandsMapped.count(U)) return;
 532   VMC.OperandsMapped.insert(U);
 533
 534   ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(U);
 535   if (VMCI != VMC.ExprMap.end())
 536     return;
 537
 538
 539   Instruction *I = cast<Instruction>(U);  // Only Instructions convertable
 540
 541   BasicBlock *BB = I->getParent();
 542   BasicBlock::InstListType &BIL = BB->getInstList();
 543   string Name = I->getName();  if (!Name.empty()) I->setName("");
 544   Instruction *Res;     // Result of conversion
 545
 546   //cerr << endl << endl << "Type:\t" << Ty << "\nInst: " << I << "BB Before: " << BB << endl;
 547
 548   // Prevent I from being removed...
 549   ValueHandle IHandle(I);
 550
 551   const Type *NewTy = NewVal->getType();
 552   ConstPoolVal *Dummy = (NewTy != Type::VoidTy) ?
 553                   ConstPoolVal::getNullConstant(NewTy) : 0;
 554
 555   switch (I->getOpcode()) {
 556   case Instruction::Cast:
 557     assert(I->getOperand(0) == OldVal);
 558     Res = new CastInst(NewVal, I->getType(), Name);
 559     break;
 560
 561   case Instruction::Add:
 562     if (OldVal == I->getOperand(0) && isa<CastInst>(I->getOperand(1))) {
 563       Res = getAddToGEPResult(NewVal->getType(),
 564                               cast<CastInst>(I->getOperand(1))->getOperand(0));
 565       if (Res) {  // If successful, this Add should be converted to a GEP.
 566         // First operand is actually the given pointer...
 567         Res->setOperand(0, NewVal);
 568         break;
 569       }
 570     }
 571     // FALLTHROUGH
 572
 573   case Instruction::Sub:
 574   case Instruction::SetEQ:
 575   case Instruction::SetNE: {
 576     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
 577                                  Dummy, Dummy, Name);
 578     VMC.ExprMap[I] = Res;   // Add node to expression eagerly
 579
 580     unsigned OtherIdx = (OldVal == I->getOperand(0)) ? 1 : 0;
 581     Value *OtherOp    = I->getOperand(OtherIdx);
 582     Value *NewOther   = ConvertExpressionToType(OtherOp, NewTy, VMC);
 583
 584     Res->setOperand(OtherIdx, NewOther);
 585     Res->setOperand(!OtherIdx, NewVal);
 586     break;
 587   }
 588   case Instruction::Shl:
 589   case Instruction::Shr:
 590     assert(I->getOperand(0) == OldVal);
 591     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), NewVal,
 592                         I->getOperand(1), Name);
 593     break;
 594
 595   case Instruction::Load: {
 596     assert(I->getOperand(0) == OldVal && isa<PointerType>(NewVal->getType()));
 597     const Type *PVTy = cast<PointerType>(NewVal->getType())->getValueType();
 598     if (!isFirstClassType(PVTy)) {  // Must be an indirect load then...
 599       assert(isa<StructType>(PVTy));
 600       unsigned Offset = 0;   // No offset, get first leaf.
 601       vector<ConstPoolVal*> Offsets;  // Discarded...
 602       const Type *Ty = getStructOffsetType(PVTy, Offset, Offsets, false);
 603       Res = new LoadInst(NewVal, Offsets, Name);
 604     } else {
 605       Res = new LoadInst(NewVal, Name);
 606     }
 607     assert(isFirstClassType(Res->getType()) && "Load of structure or array!");
 608     break;
 609   }
 610   case Instruction::Store: {
 611     if (I->getOperand(0) == OldVal) {  // Replace the source value
 612       const PointerType *NewPT = PointerType::get(NewTy);
 613       Res = new StoreInst(NewVal, ConstPoolVal::getNullConstant(NewPT));
 614       VMC.ExprMap[I] = Res;
 615       Res->setOperand(1, ConvertExpressionToType(I->getOperand(1), NewPT, VMC));
 616     } else {                           // Replace the source pointer
 617       const Type *ValTy = cast<PointerType>(NewTy)->getValueType();
 618       Res = new StoreInst(ConstPoolVal::getNullConstant(ValTy), NewVal);
 619       VMC.ExprMap[I] = Res;
 620       Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), ValTy, VMC));
 621     }
 622     break;
 623   }
 624
 625   case Instruction::PHINode: {
 626     PHINode *OldPN = cast<PHINode>(I);
 627     PHINode *NewPN = new PHINode(NewTy, Name);
 628     VMC.ExprMap[I] = NewPN;
 629
 630     while (OldPN->getNumOperands()) {
 631       BasicBlock *BB = OldPN->getIncomingBlock(0);
 632       Value *OldVal = OldPN->getIncomingValue(0);
 633       OldPN->removeIncomingValue(BB);
 634       Value *V = ConvertExpressionToType(OldVal, NewTy, VMC);
 635       NewPN->addIncoming(V, BB);
 636     }
 637     Res = NewPN;
 638     break;
 639   }
 640
 641 #if 0
 642   case Instruction::GetElementPtr: {
 643     // GetElementPtr's are directly convertable to a pointer type if they have
 644     // a number of zeros at the end.  Because removing these values does not
 645     // change the logical offset of the GEP, it is okay and fair to remove them.
 646     // This can change this:
 647     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 648     //   %t2 = cast %List * * %t1 to %List *
 649     // into
 650     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 651     //
 652     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 653
 654     // Check to see if there are zero elements that we can remove from the
 655     // index array.  If there are, check to see if removing them causes us to
 656     // get to the right type...
 657     //
 658     vector<ConstPoolVal*> Indices = GEP->getIndices();
 659     const Type *BaseType = GEP->getPtrOperand()->getType();
 660     const Type *PVTy = cast<PointerType>(Ty)->getValueType();
 661     Res = 0;
 662     while (Indices.size() &&
 663            cast<ConstPoolUInt>(Indices.back())->getValue() == 0) {
 664       Indices.pop_back();
 665       if (GetElementPtrInst::getIndexedType(BaseType, Indices, true) == PVTy) {
 666         if (Indices.size() == 0) {
 667           Res = new CastInst(GEP->getPtrOperand(), BaseType); // NOOP
 668         } else {
 669           Res = new GetElementPtrInst(GEP->getPtrOperand(), Indices, Name);
 670         }
 671         break;
 672       }
 673     }
 674     assert(Res && "Didn't find match!");
 675     break;   // No match, maybe next time.
 676   }
 677 #endif
 678
 679   default:
 680     assert(0 && "Expression convertable, but don't know how to convert?");
 681     return;
 682   }
 683
 684   BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 685   assert(It != BIL.end() && "Instruction not in own basic block??");
 686   BIL.insert(It, Res);   // Keep It pointing to old instruction
 687
 688 #ifdef DEBUG_EXPR_CONVERT
 689   cerr << "COT CREATED: "  << (void*)Res << " " << Res;
 690   cerr << "In: " << (void*)I << " " << I << "Out: " << (void*)Res << " " << Res;
 691 #endif
 692
 693   // Add the instruction to the expression map
 694   VMC.ExprMap[I] = Res;
 695
 696   if (I->getType() != Res->getType())
 697     ConvertUsersType(I, Res, VMC);
 698   else {
 699     for (unsigned It = 0; It < I->use_size(); ) {
 700       User *Use = *(I->use_begin()+It);
 701       if (isa<ValueHandle>(Use))            // Don't remove ValueHandles!
 702         ++It;
 703       else
 704         Use->replaceUsesOfWith(I, Res);
 705     }
 706
 707     if (I->use_empty()) {
 708       // Now we just need to remove the old instruction so we don't get infinite
 709       // loops.  Note that we cannot use DCE because DCE won't remove a store
 710       // instruction, for example.
 711       //
 712 #ifdef DEBUG_EXPR_CONVERT
 713       cerr << "DELETING: " << (void*)I << " " << I;
 714 #endif
 715       BIL.remove(I);
 716       delete I;
 717     } else {
 718       for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
 719            UI != UE; ++UI)
 720         assert(isa<ValueHandle>((Value*)*UI) && "Uses of Instruction remain!!!");
 721     }
 722   }
 723 }
 724
 725 ValueHandle::ValueHandle(Value *V) : Instruction(Type::VoidTy, UserOp1, "") {
 726 #ifdef DEBUG_EXPR_CONVERT
 727   cerr << "VH AQUIRING: " << (void*)V << " " << V;
 728 #endif
 729   Operands.push_back(Use(V, this));
 730 }
 731
 732 static void RecursiveDelete(Instruction *I) {
 733   if (!I || !I->use_empty()) return;
 734
 735   assert(I->getParent() && "Inst not in basic block!");
 736
 737 #ifdef DEBUG_EXPR_CONVERT
 738   cerr << "VH DELETING: " << (void*)I << " " << I;
 739 #endif
 740
 741   for (User::op_iterator OI = I->op_begin(), OE = I->op_end();
 742        OI != OE; ++OI) {
 743     Instruction *U = dyn_cast<Instruction>(*OI);
 744     if (U) {
 745       *OI = 0;
 746       RecursiveDelete(dyn_cast<Instruction>(U));
 747     }
 748   }
 749
 750   I->getParent()->getInstList().remove(I);
 751   delete I;
 752 }
 753
 754
 755 ValueHandle::~ValueHandle() {
 756   if (Operands[0]->use_size() == 1) {
 757     Value *V = Operands[0];
 758     Operands[0] = 0;   // Drop use!
 759
 760     // Now we just need to remove the old instruction so we don't get infinite
 761     // loops.  Note that we cannot use DCE because DCE won't remove a store
 762     // instruction, for example.
 763     //
 764     RecursiveDelete(dyn_cast<Instruction>(V));
 765   } else {
 766 #ifdef DEBUG_EXPR_CONVERT
 767     cerr << "VH RELEASING: " << (void*)Operands[0].get() << " " << Operands[0]->use_size() << " " << Operands[0];
 768 #endif
 769   }
 770 }