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/iOther.h"
  12 #include "llvm/iPHINode.h"
  13 #include "llvm/iMemory.h"
  14 #include "llvm/ConstantVals.h"
  15 #include "llvm/Optimizations/ConstantHandling.h"
  16 #include "llvm/Optimizations/DCE.h"
  17 #include "llvm/Analysis/Expressions.h"
  18 #include "Support/STLExtras.h"
  19 #include <map>
  20 #include <algorithm>
  21
  22 #include "llvm/Assembly/Writer.h"
  23
  24 //#define DEBUG_EXPR_CONVERT 1
  25
  26 static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
  27                                      ValueTypeCache &ConvertedTypes);
  28
  29 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
  30                                  ValueMapCache &VMC);
  31
  32 // AllIndicesZero - Return true if all of the indices of the specified memory
  33 // access instruction are zero, indicating an effectively nil offset to the
  34 // pointer value.
  35 //
  36 static bool AllIndicesZero(const MemAccessInst *MAI) {
  37   for (User::const_op_iterator S = MAI->idx_begin(), E = MAI->idx_end();
  38        S != E; ++S)
  39     if (!isa<Constant>(*S) || !cast<Constant>(*S)->isNullValue())
  40       return false;
  41   return true;
  42 }
  43
  44 static unsigned getBaseTypeSize(const Type *Ty) {
  45   if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty))
  46     if (ATy->isUnsized())
  47       return getBaseTypeSize(ATy->getElementType());
  48   return TD.getTypeSize(Ty);
  49 }
  50
  51
  52 // Peephole Malloc instructions: we take a look at the use chain of the
  53 // malloc instruction, and try to find out if the following conditions hold:
  54 //   1. The malloc is of the form: 'malloc [sbyte], uint <constant>'
  55 //   2. The only users of the malloc are cast & add instructions
  56 //   3. Of the cast instructions, there is only one destination pointer type
  57 //      [RTy] where the size of the pointed to object is equal to the number
  58 //      of bytes allocated.
  59 //
  60 // If these conditions hold, we convert the malloc to allocate an [RTy]
  61 // element.  TODO: This comment is out of date WRT arrays
  62 //
  63 static bool MallocConvertableToType(MallocInst *MI, const Type *Ty,
  64                                     ValueTypeCache &CTMap) {
  65   if (!MI->isArrayAllocation() ||            // No array allocation?
  66       !isa<PointerType>(Ty)) return false;   // Malloc always returns pointers
  67
  68   // Deal with the type to allocate, not the pointer type...
  69   Ty = cast<PointerType>(Ty)->getElementType();
  70
  71   // Analyze the number of bytes allocated...
  72   analysis::ExprType Expr = analysis::ClassifyExpression(MI->getArraySize());
  73
  74   // Must have a scale or offset to analyze it...
  75   if (!Expr.Offset && !Expr.Scale) return false;
  76
  77   if (Expr.Offset && (Expr.Scale || Expr.Var)) {
  78     // This is wierd, shouldn't happen, but if it does, I wanna know about it!
  79     cerr << "LevelRaise.cpp: Crazy allocation detected!\n";
  80     return false;
  81   }
  82
  83   // Get the number of bytes allocated...
  84   int SizeVal = getConstantValue(Expr.Offset ? Expr.Offset : Expr.Scale);
  85   if (SizeVal <= 0) {
  86     cerr << "malloc of a negative number???\n";
  87     return false;
  88   }
  89   unsigned Size = (unsigned)SizeVal;
  90   unsigned ReqTypeSize = getBaseTypeSize(Ty);
  91
  92   // Does the size of the allocated type match the number of bytes
  93   // allocated?
  94   //
  95   if (ReqTypeSize == Size)
  96     return true;
  97
  98   // If not, it's possible that an array of constant size is being allocated.
  99   // In this case, the Size will be a multiple of the data size.
 100   //
 101   if (!Expr.Offset) return false;  // Offset must be set, not scale...
 102
 103 #if 1
 104   return false;
 105 #else   // THIS CAN ONLY BE RUN VERY LATE, after several passes to make sure
 106         // things are adequately raised!
 107   // See if the allocated amount is a multiple of the type size...
 108   if (Size/ReqTypeSize*ReqTypeSize != Size)
 109     return false;   // Nope.
 110
 111   // Unfortunately things tend to be powers of two, so there may be
 112   // many false hits.  We don't want to optimistically assume that we
 113   // have the right type on the first try, so scan the use list of the
 114   // malloc instruction, looking for the cast to the biggest type...
 115   //
 116   for (Value::use_iterator I = MI->use_begin(), E = MI->use_end(); I != E; ++I)
 117     if (CastInst *CI = dyn_cast<CastInst>(*I))
 118       if (const PointerType *PT =
 119           dyn_cast<PointerType>(CI->getOperand(0)->getType()))
 120         if (getBaseTypeSize(PT->getElementType()) > ReqTypeSize)
 121           return false;     // We found a type bigger than this one!
 122
 123   return true;
 124 #endif
 125 }
 126
 127 static Instruction *ConvertMallocToType(MallocInst *MI, const Type *Ty,
 128                                         const string &Name, ValueMapCache &VMC){
 129   BasicBlock *BB = MI->getParent();
 130   BasicBlock::iterator It = BB->end();
 131
 132   // Analyze the number of bytes allocated...
 133   analysis::ExprType Expr = analysis::ClassifyExpression(MI->getArraySize());
 134
 135   const PointerType *AllocTy = cast<PointerType>(Ty);
 136   const Type *ElType = AllocTy->getElementType();
 137
 138   if (Expr.Var && !isa<ArrayType>(ElType)) {
 139     ElType = ArrayType::get(AllocTy->getElementType());
 140     AllocTy = PointerType::get(ElType);
 141   }
 142
 143   // If the array size specifier is not an unsigned integer, insert a cast now.
 144   if (Expr.Var && Expr.Var->getType() != Type::UIntTy) {
 145     It = find(BB->getInstList().begin(), BB->getInstList().end(), MI);
 146     CastInst *SizeCast = new CastInst(Expr.Var, Type::UIntTy);
 147     It = BB->getInstList().insert(It, SizeCast)+1;
 148     Expr.Var = SizeCast;
 149   }
 150
 151   // Check to see if they are allocating a constant sized array of a type...
 152 #if 0   // THIS CAN ONLY BE RUN VERY LATE
 153   if (!Expr.Var) {
 154     unsigned OffsetAmount  = (unsigned)getConstantValue(Expr.Offset);
 155     unsigned DataSize = TD.getTypeSize(ElType);
 156
 157     if (OffsetAmount > DataSize) // Allocate a sized array amount...
 158       Expr.Var = ConstantUInt::get(Type::UIntTy, OffsetAmount/DataSize);
 159   }
 160 #endif
 161
 162   Instruction *NewI = new MallocInst(AllocTy, Expr.Var, Name);
 163
 164   if (AllocTy != Ty) { // Create a cast instruction to cast it to the correct ty
 165     if (It == BB->end())
 166       It = find(BB->getInstList().begin(), BB->getInstList().end(), MI);
 167
 168     // Insert the new malloc directly into the code ourselves
 169     assert(It != BB->getInstList().end());
 170     It = BB->getInstList().insert(It, NewI)+1;
 171
 172     // Return the cast as the value to use...
 173     NewI = new CastInst(NewI, Ty);
 174   }
 175
 176   return NewI;
 177 }
 178
 179
 180 // ExpressionConvertableToType - Return true if it is possible
 181 bool ExpressionConvertableToType(Value *V, const Type *Ty,
 182                                  ValueTypeCache &CTMap) {
 183   if (V->getType() == Ty) return true;  // Expression already correct type!
 184
 185   // Expression type must be holdable in a register.
 186   if (!isFirstClassType(Ty))
 187     return false;
 188
 189   ValueTypeCache::iterator CTMI = CTMap.find(V);
 190   if (CTMI != CTMap.end()) return CTMI->second == Ty;
 191
 192   CTMap[V] = Ty;
 193
 194   Instruction *I = dyn_cast<Instruction>(V);
 195   if (I == 0) {
 196     // It's not an instruction, check to see if it's a constant... all constants
 197     // can be converted to an equivalent value (except pointers, they can't be
 198     // const prop'd in general).  We just ask the constant propogator to see if
 199     // it can convert the value...
 200     //
 201     if (Constant *CPV = dyn_cast<Constant>(V))
 202       if (opt::ConstantFoldCastInstruction(CPV, Ty))
 203         return true;  // Don't worry about deallocating, it's a constant.
 204
 205     return false;              // Otherwise, we can't convert!
 206   }
 207
 208   switch (I->getOpcode()) {
 209   case Instruction::Cast:
 210     // We can convert the expr if the cast destination type is losslessly
 211     // convertable to the requested type.
 212     if (!Ty->isLosslesslyConvertableTo(I->getType())) return false;
 213 #if 1
 214     // We also do not allow conversion of a cast that casts from a ptr to array
 215     // of X to a *X.  For example: cast [4 x %List *] * %val to %List * *
 216     //
 217     if (PointerType *SPT = dyn_cast<PointerType>(I->getOperand(0)->getType()))
 218       if (PointerType *DPT = dyn_cast<PointerType>(I->getType()))
 219         if (ArrayType *AT = dyn_cast<ArrayType>(SPT->getElementType()))
 220           if (AT->getElementType() == DPT->getElementType())
 221             return false;
 222 #endif
 223     break;
 224
 225   case Instruction::Add:
 226   case Instruction::Sub:
 227     if (!ExpressionConvertableToType(I->getOperand(0), Ty, CTMap) ||
 228         !ExpressionConvertableToType(I->getOperand(1), Ty, CTMap))
 229       return false;
 230     break;
 231   case Instruction::Shr:
 232     if (Ty->isSigned() != V->getType()->isSigned()) return false;
 233     // FALL THROUGH
 234   case Instruction::Shl:
 235     if (!ExpressionConvertableToType(I->getOperand(0), Ty, CTMap))
 236       return false;
 237     break;
 238
 239   case Instruction::Load: {
 240     LoadInst *LI = cast<LoadInst>(I);
 241     if (LI->hasIndices() && !AllIndicesZero(LI)) {
 242       // We can't convert a load expression if it has indices... unless they are
 243       // all zero.
 244       return false;
 245     }
 246
 247     if (!ExpressionConvertableToType(LI->getPointerOperand(),
 248                                      PointerType::get(Ty), CTMap))
 249       return false;
 250     break;
 251   }
 252   case Instruction::PHINode: {
 253     PHINode *PN = cast<PHINode>(I);
 254     for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i)
 255       if (!ExpressionConvertableToType(PN->getIncomingValue(i), Ty, CTMap))
 256         return false;
 257     break;
 258   }
 259
 260   case Instruction::Malloc:
 261     if (!MallocConvertableToType(cast<MallocInst>(I), Ty, CTMap))
 262       return false;
 263     break;
 264
 265 #if 1
 266   case Instruction::GetElementPtr: {
 267     // GetElementPtr's are directly convertable to a pointer type if they have
 268     // a number of zeros at the end.  Because removing these values does not
 269     // change the logical offset of the GEP, it is okay and fair to remove them.
 270     // This can change this:
 271     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 272     //   %t2 = cast %List * * %t1 to %List *
 273     // into
 274     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 275     //
 276     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 277     const PointerType *PTy = dyn_cast<PointerType>(Ty);
 278     if (!PTy) return false;
 279
 280     // Check to see if there are zero elements that we can remove from the
 281     // index array.  If there are, check to see if removing them causes us to
 282     // get to the right type...
 283     //
 284     vector<Value*> Indices = GEP->copyIndices();
 285     const Type *BaseType = GEP->getPointerOperand()->getType();
 286     const Type *ElTy = 0;
 287
 288     while (!Indices.empty() && isa<ConstantUInt>(Indices.back()) &&
 289            cast<ConstantUInt>(Indices.back())->getValue() == 0) {
 290       Indices.pop_back();
 291       ElTy = GetElementPtrInst::getIndexedType(BaseType, Indices,
 292                                                            true);
 293       if (ElTy == PTy->getElementType())
 294         break;  // Found a match!!
 295       ElTy = 0;
 296     }
 297
 298     if (ElTy) break;
 299     return false;   // No match, maybe next time.
 300   }
 301 #endif
 302
 303   default:
 304     return false;
 305   }
 306
 307   // Expressions are only convertable if all of the users of the expression can
 308   // have this value converted.  This makes use of the map to avoid infinite
 309   // recursion.
 310   //
 311   for (Value::use_iterator It = I->use_begin(), E = I->use_end(); It != E; ++It)
 312     if (!OperandConvertableToType(*It, I, Ty, CTMap))
 313       return false;
 314
 315   return true;
 316 }
 317
 318
 319 Value *ConvertExpressionToType(Value *V, const Type *Ty, ValueMapCache &VMC) {
 320   if (V->getType() == Ty) return V;  // Already where we need to be?
 321
 322   ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(V);
 323   if (VMCI != VMC.ExprMap.end()) {
 324     assert(VMCI->second->getType() == Ty);
 325     return VMCI->second;
 326   }
 327
 328 #ifdef DEBUG_EXPR_CONVERT
 329   cerr << "CETT: " << (void*)V << " " << V;
 330 #endif
 331
 332   Instruction *I = dyn_cast<Instruction>(V);
 333   if (I == 0)
 334     if (Constant *CPV = cast<Constant>(V)) {
 335       // Constants are converted by constant folding the cast that is required.
 336       // We assume here that all casts are implemented for constant prop.
 337       Value *Result = opt::ConstantFoldCastInstruction(CPV, Ty);
 338       assert(Result && "ConstantFoldCastInstruction Failed!!!");
 339       assert(Result->getType() == Ty && "Const prop of cast failed!");
 340
 341       // Add the instruction to the expression map
 342       VMC.ExprMap[V] = Result;
 343       return Result;
 344     }
 345
 346
 347   BasicBlock *BB = I->getParent();
 348   BasicBlock::InstListType &BIL = BB->getInstList();
 349   string Name = I->getName();  if (!Name.empty()) I->setName("");
 350   Instruction *Res;     // Result of conversion
 351
 352   ValueHandle IHandle(VMC, I);  // Prevent I from being removed!
 353
 354   Constant *Dummy = Constant::getNullConstant(Ty);
 355
 356   //cerr << endl << endl << "Type:\t" << Ty << "\nInst: " << I << "BB Before: " << BB << endl;
 357
 358   switch (I->getOpcode()) {
 359   case Instruction::Cast:
 360     Res = new CastInst(I->getOperand(0), Ty, Name);
 361     break;
 362
 363   case Instruction::Add:
 364   case Instruction::Sub:
 365     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
 366                                  Dummy, Dummy, Name);
 367     VMC.ExprMap[I] = Res;   // Add node to expression eagerly
 368
 369     Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC));
 370     Res->setOperand(1, ConvertExpressionToType(I->getOperand(1), Ty, VMC));
 371     break;
 372
 373   case Instruction::Shl:
 374   case Instruction::Shr:
 375     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), Dummy,
 376                         I->getOperand(1), Name);
 377     VMC.ExprMap[I] = Res;
 378     Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC));
 379     break;
 380
 381   case Instruction::Load: {
 382     LoadInst *LI = cast<LoadInst>(I);
 383     assert(!LI->hasIndices() || AllIndicesZero(LI));
 384
 385     Res = new LoadInst(Constant::getNullConstant(PointerType::get(Ty)), Name);
 386     VMC.ExprMap[I] = Res;
 387     Res->setOperand(0, ConvertExpressionToType(LI->getPointerOperand(),
 388                                                PointerType::get(Ty), VMC));
 389     assert(Res->getOperand(0)->getType() == PointerType::get(Ty));
 390     assert(Ty == Res->getType());
 391     assert(isFirstClassType(Res->getType()) && "Load of structure or array!");
 392     break;
 393   }
 394
 395   case Instruction::PHINode: {
 396     PHINode *OldPN = cast<PHINode>(I);
 397     PHINode *NewPN = new PHINode(Ty, Name);
 398
 399     VMC.ExprMap[I] = NewPN;   // Add node to expression eagerly
 400     while (OldPN->getNumOperands()) {
 401       BasicBlock *BB = OldPN->getIncomingBlock(0);
 402       Value *OldVal = OldPN->getIncomingValue(0);
 403       ValueHandle OldValHandle(VMC, OldVal);
 404       OldPN->removeIncomingValue(BB);
 405       Value *V = ConvertExpressionToType(OldVal, Ty, VMC);
 406       NewPN->addIncoming(V, BB);
 407     }
 408     Res = NewPN;
 409     break;
 410   }
 411
 412   case Instruction::Malloc: {
 413     Res = ConvertMallocToType(cast<MallocInst>(I), Ty, Name, VMC);
 414     break;
 415   }
 416
 417   case Instruction::GetElementPtr: {
 418     // GetElementPtr's are directly convertable to a pointer type if they have
 419     // a number of zeros at the end.  Because removing these values does not
 420     // change the logical offset of the GEP, it is okay and fair to remove them.
 421     // This can change this:
 422     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 423     //   %t2 = cast %List * * %t1 to %List *
 424     // into
 425     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 426     //
 427     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 428
 429     // Check to see if there are zero elements that we can remove from the
 430     // index array.  If there are, check to see if removing them causes us to
 431     // get to the right type...
 432     //
 433     vector<Value*> Indices = GEP->copyIndices();
 434     const Type *BaseType = GEP->getPointerOperand()->getType();
 435     const Type *PVTy = cast<PointerType>(Ty)->getElementType();
 436     Res = 0;
 437     while (!Indices.empty() && isa<ConstantUInt>(Indices.back()) &&
 438            cast<ConstantUInt>(Indices.back())->getValue() == 0) {
 439       Indices.pop_back();
 440       if (GetElementPtrInst::getIndexedType(BaseType, Indices, true) == PVTy) {
 441         if (Indices.size() == 0) {
 442           Res = new CastInst(GEP->getPointerOperand(), BaseType); // NOOP
 443         } else {
 444           Res = new GetElementPtrInst(GEP->getPointerOperand(), Indices, Name);
 445         }
 446         break;
 447       }
 448     }
 449     assert(Res && "Didn't find match!");
 450     break;   // No match, maybe next time.
 451   }
 452
 453   default:
 454     assert(0 && "Expression convertable, but don't know how to convert?");
 455     return 0;
 456   }
 457
 458   assert(Res->getType() == Ty && "Didn't convert expr to correct type!");
 459
 460   BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 461   assert(It != BIL.end() && "Instruction not in own basic block??");
 462   BIL.insert(It, Res);
 463
 464   // Add the instruction to the expression map
 465   VMC.ExprMap[I] = Res;
 466
 467   // Expressions are only convertable if all of the users of the expression can
 468   // have this value converted.  This makes use of the map to avoid infinite
 469   // recursion.
 470   //
 471   unsigned NumUses = I->use_size();
 472   for (unsigned It = 0; It < NumUses; ) {
 473     unsigned OldSize = NumUses;
 474     ConvertOperandToType(*(I->use_begin()+It), I, Res, VMC);
 475     NumUses = I->use_size();
 476     if (NumUses == OldSize) ++It;
 477   }
 478
 479 #ifdef DEBUG_EXPR_CONVERT
 480   cerr << "ExpIn: " << (void*)I << " " << I
 481        << "ExpOut: " << (void*)Res << " " << Res;
 482 #endif
 483
 484   if (I->use_empty()) {
 485 #ifdef DEBUG_EXPR_CONVERT
 486     cerr << "EXPR DELETING: " << (void*)I << " " << I;
 487 #endif
 488     BIL.remove(I);
 489     VMC.OperandsMapped.erase(I);
 490     VMC.ExprMap.erase(I);
 491     delete I;
 492   }
 493
 494   return Res;
 495 }
 496
 497
 498
 499 // ValueConvertableToType - Return true if it is possible
 500 bool ValueConvertableToType(Value *V, const Type *Ty,
 501                              ValueTypeCache &ConvertedTypes) {
 502   ValueTypeCache::iterator I = ConvertedTypes.find(V);
 503   if (I != ConvertedTypes.end()) return I->second == Ty;
 504   ConvertedTypes[V] = Ty;
 505
 506   // It is safe to convert the specified value to the specified type IFF all of
 507   // the uses of the value can be converted to accept the new typed value.
 508   //
 509   for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I)
 510     if (!OperandConvertableToType(*I, V, Ty, ConvertedTypes))
 511       return false;
 512
 513   return true;
 514 }
 515
 516
 517
 518
 519
 520 // OperandConvertableToType - Return true if it is possible to convert operand
 521 // V of User (instruction) U to the specified type.  This is true iff it is
 522 // possible to change the specified instruction to accept this.  CTMap is a map
 523 // of converted types, so that circular definitions will see the future type of
 524 // the expression, not the static current type.
 525 //
 526 static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
 527                                      ValueTypeCache &CTMap) {
 528   if (V->getType() == Ty) return true;   // Operand already the right type?
 529
 530   // Expression type must be holdable in a register.
 531   if (!isFirstClassType(Ty))
 532     return false;
 533
 534   Instruction *I = dyn_cast<Instruction>(U);
 535   if (I == 0) return false;              // We can't convert!
 536
 537   switch (I->getOpcode()) {
 538   case Instruction::Cast:
 539     assert(I->getOperand(0) == V);
 540     // We can convert the expr if the cast destination type is losslessly
 541     // convertable to the requested type.
 542     if (!Ty->isLosslesslyConvertableTo(I->getOperand(0)->getType()))
 543       return false;
 544 #if 1
 545     // We also do not allow conversion of a cast that casts from a ptr to array
 546     // of X to a *X.  For example: cast [4 x %List *] * %val to %List * *
 547     //
 548     if (PointerType *SPT = dyn_cast<PointerType>(I->getOperand(0)->getType()))
 549       if (PointerType *DPT = dyn_cast<PointerType>(I->getType()))
 550         if (ArrayType *AT = dyn_cast<ArrayType>(SPT->getElementType()))
 551           if (AT->getElementType() == DPT->getElementType())
 552             return false;
 553 #endif
 554     return true;
 555
 556   case Instruction::Add:
 557     if (isa<PointerType>(Ty)) {
 558       Value *IndexVal = I->getOperand(V == I->getOperand(0) ? 1 : 0);
 559       vector<Value*> Indices;
 560       if (const Type *ETy = ConvertableToGEP(Ty, IndexVal, Indices)) {
 561         const Type *RetTy = PointerType::get(ETy);
 562
 563         // Only successful if we can convert this type to the required type
 564         if (ValueConvertableToType(I, RetTy, CTMap)) {
 565           CTMap[I] = RetTy;
 566           return true;
 567         }
 568       }
 569     }
 570     // FALLTHROUGH
 571   case Instruction::Sub: {
 572     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
 573     return ValueConvertableToType(I, Ty, CTMap) &&
 574            ExpressionConvertableToType(OtherOp, Ty, CTMap);
 575   }
 576   case Instruction::SetEQ:
 577   case Instruction::SetNE: {
 578     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
 579     return ExpressionConvertableToType(OtherOp, Ty, CTMap);
 580   }
 581   case Instruction::Shr:
 582     if (Ty->isSigned() != V->getType()->isSigned()) return false;
 583     // FALL THROUGH
 584   case Instruction::Shl:
 585     assert(I->getOperand(0) == V);
 586     return ValueConvertableToType(I, Ty, CTMap);
 587
 588   case Instruction::Load:
 589     // Cannot convert the types of any subscripts...
 590     if (I->getOperand(0) != V) return false;
 591
 592     if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
 593       LoadInst *LI = cast<LoadInst>(I);
 594
 595       if (LI->hasIndices() && !AllIndicesZero(LI))
 596         return false;
 597
 598       const Type *LoadedTy = PT->getElementType();
 599
 600       // They could be loading the first element of a composite type...
 601       if (const CompositeType *CT = dyn_cast<CompositeType>(LoadedTy)) {
 602         unsigned Offset = 0;     // No offset, get first leaf.
 603         vector<Value*> Indices;  // Discarded...
 604         LoadedTy = getStructOffsetType(CT, Offset, Indices, false);
 605         assert(Offset == 0 && "Offset changed from zero???");
 606       }
 607
 608       if (!isFirstClassType(LoadedTy))
 609         return false;
 610
 611       if (TD.getTypeSize(LoadedTy) != TD.getTypeSize(LI->getType()))
 612         return false;
 613
 614       return ValueConvertableToType(LI, LoadedTy, CTMap);
 615     }
 616     return false;
 617
 618   case Instruction::Store: {
 619     StoreInst *SI = cast<StoreInst>(I);
 620     if (SI->hasIndices()) return false;
 621
 622     if (V == I->getOperand(0)) {
 623       // Can convert the store if we can convert the pointer operand to match
 624       // the new  value type...
 625       return ExpressionConvertableToType(I->getOperand(1), PointerType::get(Ty),
 626                                          CTMap);
 627     } else if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
 628       const Type *ElTy = PT->getElementType();
 629       if (ArrayType *AT = dyn_cast<ArrayType>(ElTy))
 630         ElTy = AT->getElementType(); // Avoid getDataSize on unsized array type!
 631       assert(V == I->getOperand(1));
 632
 633       // Must move the same amount of data...
 634       if (TD.getTypeSize(ElTy) != TD.getTypeSize(I->getOperand(0)->getType()))
 635         return false;
 636
 637       // Can convert store if the incoming value is convertable...
 638       return ExpressionConvertableToType(I->getOperand(0), ElTy, CTMap);
 639     }
 640     return false;
 641   }
 642
 643   case Instruction::GetElementPtr:
 644     // Convert a getelementptr [sbyte] * %reg111, uint 16 freely back to
 645     // anything that is a pointer type...
 646     //
 647     if (I->getType() != PointerType::get(Type::SByteTy) ||
 648         I->getNumOperands() != 2 || V != I->getOperand(0) ||
 649         I->getOperand(1)->getType() != Type::UIntTy || !isa<PointerType>(Ty))
 650       return false;
 651     return true;
 652
 653   case Instruction::PHINode: {
 654     PHINode *PN = cast<PHINode>(I);
 655     for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i)
 656       if (!ExpressionConvertableToType(PN->getIncomingValue(i), Ty, CTMap))
 657         return false;
 658     return ValueConvertableToType(PN, Ty, CTMap);
 659   }
 660
 661   case Instruction::Call: {
 662     User::op_iterator OI = find(I->op_begin(), I->op_end(), V);
 663     assert (OI != I->op_end() && "Not using value!");
 664     unsigned OpNum = OI - I->op_begin();
 665
 666     if (OpNum == 0)
 667       return false; // Can't convert method pointer type yet.  FIXME
 668
 669     const PointerType *MPtr = cast<PointerType>(I->getOperand(0)->getType());
 670     const MethodType *MTy = cast<MethodType>(MPtr->getElementType());
 671     if (!MTy->isVarArg()) return false;
 672
 673     if ((OpNum-1) < MTy->getParamTypes().size())
 674       return false;  // It's not in the varargs section...
 675
 676     // If we get this far, we know the value is in the varargs section of the
 677     // method!  We can convert if we don't reinterpret the value...
 678     //
 679     return Ty->isLosslesslyConvertableTo(V->getType());
 680   }
 681   }
 682   return false;
 683 }
 684
 685
 686 void ConvertValueToNewType(Value *V, Value *NewVal, ValueMapCache &VMC) {
 687   ValueHandle VH(VMC, V);
 688
 689   unsigned NumUses = V->use_size();
 690   for (unsigned It = 0; It < NumUses; ) {
 691     unsigned OldSize = NumUses;
 692     ConvertOperandToType(*(V->use_begin()+It), V, NewVal, VMC);
 693     NumUses = V->use_size();
 694     if (NumUses == OldSize) ++It;
 695   }
 696 }
 697
 698
 699
 700 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
 701                                  ValueMapCache &VMC) {
 702   if (isa<ValueHandle>(U)) return;  // Valuehandles don't let go of operands...
 703
 704   if (VMC.OperandsMapped.count(U)) return;
 705   VMC.OperandsMapped.insert(U);
 706
 707   ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(U);
 708   if (VMCI != VMC.ExprMap.end())
 709     return;
 710
 711
 712   Instruction *I = cast<Instruction>(U);  // Only Instructions convertable
 713
 714   BasicBlock *BB = I->getParent();
 715   BasicBlock::InstListType &BIL = BB->getInstList();
 716   string Name = I->getName();  if (!Name.empty()) I->setName("");
 717   Instruction *Res;     // Result of conversion
 718
 719   //cerr << endl << endl << "Type:\t" << Ty << "\nInst: " << I << "BB Before: " << BB << endl;
 720
 721   // Prevent I from being removed...
 722   ValueHandle IHandle(VMC, I);
 723
 724   const Type *NewTy = NewVal->getType();
 725   Constant *Dummy = (NewTy != Type::VoidTy) ?
 726                   Constant::getNullConstant(NewTy) : 0;
 727
 728   switch (I->getOpcode()) {
 729   case Instruction::Cast:
 730     assert(I->getOperand(0) == OldVal);
 731     Res = new CastInst(NewVal, I->getType(), Name);
 732     break;
 733
 734   case Instruction::Add:
 735     if (isa<PointerType>(NewTy)) {
 736       Value *IndexVal = I->getOperand(OldVal == I->getOperand(0) ? 1 : 0);
 737       vector<Value*> Indices;
 738       BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 739
 740       if (const Type *ETy = ConvertableToGEP(NewTy, IndexVal, Indices, &It)) {
 741         // If successful, convert the add to a GEP
 742         const Type *RetTy = PointerType::get(ETy);
 743         // First operand is actually the given pointer...
 744         Res = new GetElementPtrInst(NewVal, Indices, Name);
 745         assert(cast<PointerType>(Res->getType())->getElementType() == ETy &&
 746                "ConvertableToGEP broken!");
 747         break;
 748       }
 749     }
 750     // FALLTHROUGH
 751
 752   case Instruction::Sub:
 753   case Instruction::SetEQ:
 754   case Instruction::SetNE: {
 755     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
 756                                  Dummy, Dummy, Name);
 757     VMC.ExprMap[I] = Res;   // Add node to expression eagerly
 758
 759     unsigned OtherIdx = (OldVal == I->getOperand(0)) ? 1 : 0;
 760     Value *OtherOp    = I->getOperand(OtherIdx);
 761     Value *NewOther   = ConvertExpressionToType(OtherOp, NewTy, VMC);
 762
 763     Res->setOperand(OtherIdx, NewOther);
 764     Res->setOperand(!OtherIdx, NewVal);
 765     break;
 766   }
 767   case Instruction::Shl:
 768   case Instruction::Shr:
 769     assert(I->getOperand(0) == OldVal);
 770     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), NewVal,
 771                         I->getOperand(1), Name);
 772     break;
 773
 774   case Instruction::Load: {
 775     assert(I->getOperand(0) == OldVal && isa<PointerType>(NewVal->getType()));
 776     const Type *LoadedTy = cast<PointerType>(NewVal->getType())->getElementType();
 777
 778     vector<Value*> Indices;
 779
 780     if (const CompositeType *CT = dyn_cast<CompositeType>(LoadedTy)) {
 781       unsigned Offset = 0;   // No offset, get first leaf.
 782       LoadedTy = getStructOffsetType(CT, Offset, Indices, false);
 783     }
 784     assert(isFirstClassType(LoadedTy));
 785
 786     Res = new LoadInst(NewVal, Indices, Name);
 787     assert(isFirstClassType(Res->getType()) && "Load of structure or array!");
 788     break;
 789   }
 790
 791   case Instruction::Store: {
 792     if (I->getOperand(0) == OldVal) {  // Replace the source value
 793       const PointerType *NewPT = PointerType::get(NewTy);
 794       Res = new StoreInst(NewVal, Constant::getNullConstant(NewPT));
 795       VMC.ExprMap[I] = Res;
 796       Res->setOperand(1, ConvertExpressionToType(I->getOperand(1), NewPT, VMC));
 797     } else {                           // Replace the source pointer
 798       const Type *ValTy = cast<PointerType>(NewTy)->getElementType();
 799       vector<Value*> Indices;
 800       while (ArrayType *AT = dyn_cast<ArrayType>(ValTy)) {
 801         Indices.push_back(ConstantUInt::get(Type::UIntTy, 0));
 802         ValTy = AT->getElementType();
 803       }
 804
 805       Res = new StoreInst(Constant::getNullConstant(ValTy), NewVal, Indices);
 806       VMC.ExprMap[I] = Res;
 807       Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), ValTy, VMC));
 808     }
 809     break;
 810   }
 811
 812
 813   case Instruction::GetElementPtr: {
 814     // Convert a getelementptr [sbyte] * %reg111, uint 16 freely back to
 815     // anything that is a pointer type...
 816     //
 817     BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 818
 819     // Insert a cast right before this instruction of the index value...
 820     CastInst *CIdx = new CastInst(I->getOperand(1), NewTy);
 821     It = BIL.insert(It, CIdx)+1;
 822
 823     // Insert an add right before this instruction
 824     Instruction *AddInst = BinaryOperator::create(Instruction::Add, NewVal,
 825                                                   CIdx, Name);
 826     It = BIL.insert(It, AddInst)+1;
 827
 828     // Finally, cast the result back to our previous type...
 829     Res = new CastInst(AddInst, I->getType());
 830     break;
 831   }
 832
 833   case Instruction::PHINode: {
 834     PHINode *OldPN = cast<PHINode>(I);
 835     PHINode *NewPN = new PHINode(NewTy, Name);
 836     VMC.ExprMap[I] = NewPN;
 837
 838     while (OldPN->getNumOperands()) {
 839       BasicBlock *BB = OldPN->getIncomingBlock(0);
 840       Value *OldVal = OldPN->getIncomingValue(0);
 841       OldPN->removeIncomingValue(BB);
 842       Value *V = ConvertExpressionToType(OldVal, NewTy, VMC);
 843       NewPN->addIncoming(V, BB);
 844     }
 845     Res = NewPN;
 846     break;
 847   }
 848
 849   case Instruction::Call: {
 850     Value *Meth = I->getOperand(0);
 851     vector<Value*> Params(I->op_begin()+1, I->op_end());
 852
 853     vector<Value*>::iterator OI = find(Params.begin(), Params.end(), OldVal);
 854     assert (OI != Params.end() && "Not using value!");
 855
 856     *OI = NewVal;
 857     Res = new CallInst(Meth, Params, Name);
 858     break;
 859   }
 860   default:
 861     assert(0 && "Expression convertable, but don't know how to convert?");
 862     return;
 863   }
 864
 865   BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 866   assert(It != BIL.end() && "Instruction not in own basic block??");
 867   BIL.insert(It, Res);   // Keep It pointing to old instruction
 868
 869 #ifdef DEBUG_EXPR_CONVERT
 870   cerr << "COT CREATED: "  << (void*)Res << " " << Res;
 871   cerr << "In: " << (void*)I << " " << I << "Out: " << (void*)Res << " " << Res;
 872 #endif
 873
 874   // Add the instruction to the expression map
 875   VMC.ExprMap[I] = Res;
 876
 877   if (I->getType() != Res->getType())
 878     ConvertValueToNewType(I, Res, VMC);
 879   else {
 880     for (unsigned It = 0; It < I->use_size(); ) {
 881       User *Use = *(I->use_begin()+It);
 882       if (isa<ValueHandle>(Use))            // Don't remove ValueHandles!
 883         ++It;
 884       else
 885         Use->replaceUsesOfWith(I, Res);
 886     }
 887
 888     if (I->use_empty()) {
 889       // Now we just need to remove the old instruction so we don't get infinite
 890       // loops.  Note that we cannot use DCE because DCE won't remove a store
 891       // instruction, for example.
 892       //
 893 #ifdef DEBUG_EXPR_CONVERT
 894       cerr << "DELETING: " << (void*)I << " " << I;
 895 #endif
 896       BIL.remove(I);
 897       VMC.OperandsMapped.erase(I);
 898       VMC.ExprMap.erase(I);
 899       delete I;
 900     } else {
 901       for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
 902            UI != UE; ++UI)
 903         assert(isa<ValueHandle>((Value*)*UI) &&"Uses of Instruction remain!!!");
 904     }
 905   }
 906 }
 907
 908
 909 ValueHandle::ValueHandle(ValueMapCache &VMC, Value *V)
 910   : Instruction(Type::VoidTy, UserOp1, ""), Cache(VMC) {
 911 #ifdef DEBUG_EXPR_CONVERT
 912   //cerr << "VH AQUIRING: " << (void*)V << " " << V;
 913 #endif
 914   Operands.push_back(Use(V, this));
 915 }
 916
 917 static void RecursiveDelete(ValueMapCache &Cache, Instruction *I) {
 918   if (!I || !I->use_empty()) return;
 919
 920   assert(I->getParent() && "Inst not in basic block!");
 921
 922 #ifdef DEBUG_EXPR_CONVERT
 923   //cerr << "VH DELETING: " << (void*)I << " " << I;
 924 #endif
 925
 926   for (User::op_iterator OI = I->op_begin(), OE = I->op_end();
 927        OI != OE; ++OI) {
 928     Instruction *U = dyn_cast<Instruction>(*OI);
 929     if (U) {
 930       *OI = 0;
 931       RecursiveDelete(Cache, dyn_cast<Instruction>(U));
 932     }
 933   }
 934
 935   I->getParent()->getInstList().remove(I);
 936
 937   Cache.OperandsMapped.erase(I);
 938   Cache.ExprMap.erase(I);
 939   delete I;
 940 }
 941
 942 ValueHandle::~ValueHandle() {
 943   if (Operands[0]->use_size() == 1) {
 944     Value *V = Operands[0];
 945     Operands[0] = 0;   // Drop use!
 946
 947     // Now we just need to remove the old instruction so we don't get infinite
 948     // loops.  Note that we cannot use DCE because DCE won't remove a store
 949     // instruction, for example.
 950     //
 951     RecursiveDelete(Cache, dyn_cast<Instruction>(V));
 952   } else {
 953 #ifdef DEBUG_EXPR_CONVERT
 954     //cerr << "VH RELEASING: " << (void*)Operands[0].get() << " " << Operands[0]->use_size() << " " << Operands[0];
 955 #endif
 956   }
 957 }