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