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