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