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::op_const_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)->getValueType();
  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->getValueType()) > 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->getValueType();
 137
 138   if (Expr.Var && !isa<ArrayType>(ElType)) {
 139     ElType = ArrayType::get(AllocTy->getValueType());
 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->getValueType()))
 220           if (AT->getElementType() == DPT->getValueType())
 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->getValueType())
 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   ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(V);
 321   if (VMCI != VMC.ExprMap.end()) {
 322     assert(VMCI->second->getType() == Ty);
 323     return VMCI->second;
 324   }
 325
 326 #ifdef DEBUG_EXPR_CONVERT
 327   cerr << "CETT: " << (void*)V << " " << V;
 328 #endif
 329
 330   Instruction *I = dyn_cast<Instruction>(V);
 331   if (I == 0)
 332     if (Constant *CPV = cast<Constant>(V)) {
 333       // Constants are converted by constant folding the cast that is required.
 334       // We assume here that all casts are implemented for constant prop.
 335       Value *Result = opt::ConstantFoldCastInstruction(CPV, Ty);
 336       assert(Result && "ConstantFoldCastInstruction Failed!!!");
 337       assert(Result->getType() == Ty && "Const prop of cast failed!");
 338
 339       // Add the instruction to the expression map
 340       VMC.ExprMap[V] = Result;
 341       return Result;
 342     }
 343
 344
 345   BasicBlock *BB = I->getParent();
 346   BasicBlock::InstListType &BIL = BB->getInstList();
 347   string Name = I->getName();  if (!Name.empty()) I->setName("");
 348   Instruction *Res;     // Result of conversion
 349
 350   ValueHandle IHandle(VMC, I);  // Prevent I from being removed!
 351
 352   Constant *Dummy = Constant::getNullConstant(Ty);
 353
 354   //cerr << endl << endl << "Type:\t" << Ty << "\nInst: " << I << "BB Before: " << BB << endl;
 355
 356   switch (I->getOpcode()) {
 357   case Instruction::Cast:
 358     Res = new CastInst(I->getOperand(0), Ty, Name);
 359     break;
 360
 361   case Instruction::Add:
 362   case Instruction::Sub:
 363     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
 364                                  Dummy, Dummy, Name);
 365     VMC.ExprMap[I] = Res;   // Add node to expression eagerly
 366
 367     Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC));
 368     Res->setOperand(1, ConvertExpressionToType(I->getOperand(1), Ty, VMC));
 369     break;
 370
 371   case Instruction::Shl:
 372   case Instruction::Shr:
 373     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), Dummy,
 374                         I->getOperand(1), Name);
 375     VMC.ExprMap[I] = Res;
 376     Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC));
 377     break;
 378
 379   case Instruction::Load: {
 380     LoadInst *LI = cast<LoadInst>(I);
 381     assert(!LI->hasIndices() || AllIndicesZero(LI));
 382
 383     Res = new LoadInst(Constant::getNullConstant(PointerType::get(Ty)), 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<ConstantUInt>(Indices.back()) &&
 436            cast<ConstantUInt>(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   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 (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, Constant::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(Constant::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 }