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   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)->getElementType();
 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 #endif
 481
 482   if (I->use_empty()) {
 483 #ifdef DEBUG_EXPR_CONVERT
 484     cerr << "EXPR DELETING: " << (void*)I << " " << I;
 485 #endif
 486     BIL.remove(I);
 487     VMC.OperandsMapped.erase(I);
 488     VMC.ExprMap.erase(I);
 489     delete I;
 490   }
 491
 492   return Res;
 493 }
 494
 495
 496
 497 // ValueConvertableToType - Return true if it is possible
 498 bool ValueConvertableToType(Value *V, const Type *Ty,
 499                              ValueTypeCache &ConvertedTypes) {
 500   ValueTypeCache::iterator I = ConvertedTypes.find(V);
 501   if (I != ConvertedTypes.end()) return I->second == Ty;
 502   ConvertedTypes[V] = Ty;
 503
 504   // It is safe to convert the specified value to the specified type IFF all of
 505   // the uses of the value can be converted to accept the new typed value.
 506   //
 507   for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I)
 508     if (!OperandConvertableToType(*I, V, Ty, ConvertedTypes))
 509       return false;
 510
 511   return true;
 512 }
 513
 514
 515
 516
 517
 518 // OperandConvertableToType - Return true if it is possible to convert operand
 519 // V of User (instruction) U to the specified type.  This is true iff it is
 520 // possible to change the specified instruction to accept this.  CTMap is a map
 521 // of converted types, so that circular definitions will see the future type of
 522 // the expression, not the static current type.
 523 //
 524 static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
 525                                      ValueTypeCache &CTMap) {
 526   if (V->getType() == Ty) return true;   // Operand already the right type?
 527
 528   // Expression type must be holdable in a register.
 529   if (!isFirstClassType(Ty))
 530     return false;
 531
 532   Instruction *I = dyn_cast<Instruction>(U);
 533   if (I == 0) return false;              // We can't convert!
 534
 535   switch (I->getOpcode()) {
 536   case Instruction::Cast:
 537     assert(I->getOperand(0) == V);
 538     // We can convert the expr if the cast destination type is losslessly
 539     // convertable to the requested type.
 540     if (!Ty->isLosslesslyConvertableTo(I->getOperand(0)->getType()))
 541       return false;
 542 #if 1
 543     // We also do not allow conversion of a cast that casts from a ptr to array
 544     // of X to a *X.  For example: cast [4 x %List *] * %val to %List * *
 545     //
 546     if (PointerType *SPT = dyn_cast<PointerType>(I->getOperand(0)->getType()))
 547       if (PointerType *DPT = dyn_cast<PointerType>(I->getType()))
 548         if (ArrayType *AT = dyn_cast<ArrayType>(SPT->getElementType()))
 549           if (AT->getElementType() == DPT->getElementType())
 550             return false;
 551 #endif
 552     return true;
 553
 554   case Instruction::Add:
 555     if (isa<PointerType>(Ty)) {
 556       Value *IndexVal = I->getOperand(V == I->getOperand(0) ? 1 : 0);
 557       vector<Value*> Indices;
 558       if (const Type *ETy = ConvertableToGEP(Ty, IndexVal, Indices)) {
 559         const Type *RetTy = PointerType::get(ETy);
 560
 561         // Only successful if we can convert this type to the required type
 562         if (ValueConvertableToType(I, RetTy, CTMap)) {
 563           CTMap[I] = RetTy;
 564           return true;
 565         }
 566       }
 567     }
 568     // FALLTHROUGH
 569   case Instruction::Sub: {
 570     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
 571     return ValueConvertableToType(I, Ty, CTMap) &&
 572            ExpressionConvertableToType(OtherOp, Ty, CTMap);
 573   }
 574   case Instruction::SetEQ:
 575   case Instruction::SetNE: {
 576     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
 577     return ExpressionConvertableToType(OtherOp, Ty, CTMap);
 578   }
 579   case Instruction::Shr:
 580     if (Ty->isSigned() != V->getType()->isSigned()) return false;
 581     // FALL THROUGH
 582   case Instruction::Shl:
 583     assert(I->getOperand(0) == V);
 584     return ValueConvertableToType(I, Ty, CTMap);
 585
 586   case Instruction::Load:
 587     // Cannot convert the types of any subscripts...
 588     if (I->getOperand(0) != V) return false;
 589
 590     if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
 591       LoadInst *LI = cast<LoadInst>(I);
 592
 593       if (LI->hasIndices() && !AllIndicesZero(LI))
 594         return false;
 595
 596       const Type *LoadedTy = PT->getElementType();
 597
 598       // They could be loading the first element of a composite type...
 599       if (const CompositeType *CT = dyn_cast<CompositeType>(LoadedTy)) {
 600         unsigned Offset = 0;     // No offset, get first leaf.
 601         vector<Value*> Indices;  // Discarded...
 602         LoadedTy = getStructOffsetType(CT, Offset, Indices, false);
 603         assert(Offset == 0 && "Offset changed from zero???");
 604       }
 605
 606       if (!isFirstClassType(LoadedTy))
 607         return false;
 608
 609       if (TD.getTypeSize(LoadedTy) != TD.getTypeSize(LI->getType()))
 610         return false;
 611
 612       return ValueConvertableToType(LI, LoadedTy, CTMap);
 613     }
 614     return false;
 615
 616   case Instruction::Store: {
 617     StoreInst *SI = cast<StoreInst>(I);
 618     if (SI->hasIndices()) return false;
 619
 620     if (V == I->getOperand(0)) {
 621       // Can convert the store if we can convert the pointer operand to match
 622       // the new  value type...
 623       return ExpressionConvertableToType(I->getOperand(1), PointerType::get(Ty),
 624                                          CTMap);
 625     } else if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
 626       if (isa<ArrayType>(PT->getElementType()))
 627         return false;  // Avoid getDataSize on unsized array type!
 628       assert(V == I->getOperand(1));
 629
 630       // Must move the same amount of data...
 631       if (TD.getTypeSize(PT->getElementType()) !=
 632           TD.getTypeSize(I->getOperand(0)->getType())) return false;
 633
 634       // Can convert store if the incoming value is convertable...
 635       return ExpressionConvertableToType(I->getOperand(0), PT->getElementType(),
 636                                          CTMap);
 637     }
 638     return false;
 639   }
 640
 641   case Instruction::GetElementPtr:
 642     // Convert a getelementptr [sbyte] * %reg111, uint 16 freely back to
 643     // anything that is a pointer type...
 644     //
 645     if (I->getType() != PointerType::get(Type::SByteTy) ||
 646         I->getNumOperands() != 2 || V != I->getOperand(0) ||
 647         I->getOperand(1)->getType() != Type::UIntTy || !isa<PointerType>(Ty))
 648       return false;
 649     return true;
 650
 651   case Instruction::PHINode: {
 652     PHINode *PN = cast<PHINode>(I);
 653     for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i)
 654       if (!ExpressionConvertableToType(PN->getIncomingValue(i), Ty, CTMap))
 655         return false;
 656     return ValueConvertableToType(PN, Ty, CTMap);
 657   }
 658
 659   case Instruction::Call: {
 660     User::op_iterator OI = find(I->op_begin(), I->op_end(), V);
 661     assert (OI != I->op_end() && "Not using value!");
 662     unsigned OpNum = OI - I->op_begin();
 663
 664     if (OpNum == 0)
 665       return false; // Can't convert method pointer type yet.  FIXME
 666
 667     const PointerType *MPtr = cast<PointerType>(I->getOperand(0)->getType());
 668     const MethodType *MTy = cast<MethodType>(MPtr->getElementType());
 669     if (!MTy->isVarArg()) return false;
 670
 671     if ((OpNum-1) < MTy->getParamTypes().size())
 672       return false;  // It's not in the varargs section...
 673
 674     // If we get this far, we know the value is in the varargs section of the
 675     // method!  We can convert if we don't reinterpret the value...
 676     //
 677     return Ty->isLosslesslyConvertableTo(V->getType());
 678   }
 679   }
 680   return false;
 681 }
 682
 683
 684 void ConvertValueToNewType(Value *V, Value *NewVal, ValueMapCache &VMC) {
 685   ValueHandle VH(VMC, V);
 686
 687   unsigned NumUses = V->use_size();
 688   for (unsigned It = 0; It < NumUses; ) {
 689     unsigned OldSize = NumUses;
 690     ConvertOperandToType(*(V->use_begin()+It), V, NewVal, VMC);
 691     NumUses = V->use_size();
 692     if (NumUses == OldSize) ++It;
 693   }
 694 }
 695
 696
 697
 698 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
 699                                  ValueMapCache &VMC) {
 700   if (isa<ValueHandle>(U)) return;  // Valuehandles don't let go of operands...
 701
 702   if (VMC.OperandsMapped.count(U)) return;
 703   VMC.OperandsMapped.insert(U);
 704
 705   ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(U);
 706   if (VMCI != VMC.ExprMap.end())
 707     return;
 708
 709
 710   Instruction *I = cast<Instruction>(U);  // Only Instructions convertable
 711
 712   BasicBlock *BB = I->getParent();
 713   BasicBlock::InstListType &BIL = BB->getInstList();
 714   string Name = I->getName();  if (!Name.empty()) I->setName("");
 715   Instruction *Res;     // Result of conversion
 716
 717   //cerr << endl << endl << "Type:\t" << Ty << "\nInst: " << I << "BB Before: " << BB << endl;
 718
 719   // Prevent I from being removed...
 720   ValueHandle IHandle(VMC, I);
 721
 722   const Type *NewTy = NewVal->getType();
 723   Constant *Dummy = (NewTy != Type::VoidTy) ?
 724                   Constant::getNullConstant(NewTy) : 0;
 725
 726   switch (I->getOpcode()) {
 727   case Instruction::Cast:
 728     assert(I->getOperand(0) == OldVal);
 729     Res = new CastInst(NewVal, I->getType(), Name);
 730     break;
 731
 732   case Instruction::Add:
 733     if (isa<PointerType>(NewTy)) {
 734       Value *IndexVal = I->getOperand(OldVal == I->getOperand(0) ? 1 : 0);
 735       vector<Value*> Indices;
 736       BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 737
 738       if (const Type *ETy = ConvertableToGEP(NewTy, IndexVal, Indices, &It)) {
 739         // If successful, convert the add to a GEP
 740         const Type *RetTy = PointerType::get(ETy);
 741         // First operand is actually the given pointer...
 742         Res = new GetElementPtrInst(NewVal, Indices, Name);
 743         assert(cast<PointerType>(Res->getType())->getElementType() == ETy &&
 744                "ConvertableToGEP broken!");
 745         break;
 746       }
 747     }
 748     // FALLTHROUGH
 749
 750   case Instruction::Sub:
 751   case Instruction::SetEQ:
 752   case Instruction::SetNE: {
 753     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
 754                                  Dummy, Dummy, Name);
 755     VMC.ExprMap[I] = Res;   // Add node to expression eagerly
 756
 757     unsigned OtherIdx = (OldVal == I->getOperand(0)) ? 1 : 0;
 758     Value *OtherOp    = I->getOperand(OtherIdx);
 759     Value *NewOther   = ConvertExpressionToType(OtherOp, NewTy, VMC);
 760
 761     Res->setOperand(OtherIdx, NewOther);
 762     Res->setOperand(!OtherIdx, NewVal);
 763     break;
 764   }
 765   case Instruction::Shl:
 766   case Instruction::Shr:
 767     assert(I->getOperand(0) == OldVal);
 768     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), NewVal,
 769                         I->getOperand(1), Name);
 770     break;
 771
 772   case Instruction::Load: {
 773     assert(I->getOperand(0) == OldVal && isa<PointerType>(NewVal->getType()));
 774     const Type *LoadedTy = cast<PointerType>(NewVal->getType())->getElementType();
 775
 776     vector<Value*> Indices;
 777
 778     if (const CompositeType *CT = dyn_cast<CompositeType>(LoadedTy)) {
 779       unsigned Offset = 0;   // No offset, get first leaf.
 780       LoadedTy = getStructOffsetType(CT, Offset, Indices, false);
 781     }
 782     assert(isFirstClassType(LoadedTy));
 783
 784     Res = new LoadInst(NewVal, Indices, Name);
 785     assert(isFirstClassType(Res->getType()) && "Load of structure or array!");
 786     break;
 787   }
 788
 789   case Instruction::Store: {
 790     if (I->getOperand(0) == OldVal) {  // Replace the source value
 791       const PointerType *NewPT = PointerType::get(NewTy);
 792       Res = new StoreInst(NewVal, Constant::getNullConstant(NewPT));
 793       VMC.ExprMap[I] = Res;
 794       Res->setOperand(1, ConvertExpressionToType(I->getOperand(1), NewPT, VMC));
 795     } else {                           // Replace the source pointer
 796       const Type *ValTy = cast<PointerType>(NewTy)->getElementType();
 797       Res = new StoreInst(Constant::getNullConstant(ValTy), NewVal);
 798       VMC.ExprMap[I] = Res;
 799       Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), ValTy, VMC));
 800     }
 801     break;
 802   }
 803
 804
 805   case Instruction::GetElementPtr: {
 806     // Convert a getelementptr [sbyte] * %reg111, uint 16 freely back to
 807     // anything that is a pointer type...
 808     //
 809     BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 810
 811     // Insert a cast right before this instruction of the index value...
 812     CastInst *CIdx = new CastInst(I->getOperand(1), NewTy);
 813     It = BIL.insert(It, CIdx)+1;
 814
 815     // Insert an add right before this instruction
 816     Instruction *AddInst = BinaryOperator::create(Instruction::Add, NewVal,
 817                                                   CIdx, Name);
 818     It = BIL.insert(It, AddInst)+1;
 819
 820     // Finally, cast the result back to our previous type...
 821     Res = new CastInst(AddInst, I->getType());
 822     break;
 823   }
 824
 825   case Instruction::PHINode: {
 826     PHINode *OldPN = cast<PHINode>(I);
 827     PHINode *NewPN = new PHINode(NewTy, Name);
 828     VMC.ExprMap[I] = NewPN;
 829
 830     while (OldPN->getNumOperands()) {
 831       BasicBlock *BB = OldPN->getIncomingBlock(0);
 832       Value *OldVal = OldPN->getIncomingValue(0);
 833       OldPN->removeIncomingValue(BB);
 834       Value *V = ConvertExpressionToType(OldVal, NewTy, VMC);
 835       NewPN->addIncoming(V, BB);
 836     }
 837     Res = NewPN;
 838     break;
 839   }
 840
 841   case Instruction::Call: {
 842     Value *Meth = I->getOperand(0);
 843     vector<Value*> Params(I->op_begin()+1, I->op_end());
 844
 845     vector<Value*>::iterator OI = find(Params.begin(), Params.end(), OldVal);
 846     assert (OI != Params.end() && "Not using value!");
 847
 848     *OI = NewVal;
 849     Res = new CallInst(Meth, Params, Name);
 850     break;
 851   }
 852   default:
 853     assert(0 && "Expression convertable, but don't know how to convert?");
 854     return;
 855   }
 856
 857   BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 858   assert(It != BIL.end() && "Instruction not in own basic block??");
 859   BIL.insert(It, Res);   // Keep It pointing to old instruction
 860
 861 #ifdef DEBUG_EXPR_CONVERT
 862   cerr << "COT CREATED: "  << (void*)Res << " " << Res;
 863   cerr << "In: " << (void*)I << " " << I << "Out: " << (void*)Res << " " << Res;
 864 #endif
 865
 866   // Add the instruction to the expression map
 867   VMC.ExprMap[I] = Res;
 868
 869   if (I->getType() != Res->getType())
 870     ConvertValueToNewType(I, Res, VMC);
 871   else {
 872     for (unsigned It = 0; It < I->use_size(); ) {
 873       User *Use = *(I->use_begin()+It);
 874       if (isa<ValueHandle>(Use))            // Don't remove ValueHandles!
 875         ++It;
 876       else
 877         Use->replaceUsesOfWith(I, Res);
 878     }
 879
 880     if (I->use_empty()) {
 881       // Now we just need to remove the old instruction so we don't get infinite
 882       // loops.  Note that we cannot use DCE because DCE won't remove a store
 883       // instruction, for example.
 884       //
 885 #ifdef DEBUG_EXPR_CONVERT
 886       cerr << "DELETING: " << (void*)I << " " << I;
 887 #endif
 888       BIL.remove(I);
 889       VMC.OperandsMapped.erase(I);
 890       VMC.ExprMap.erase(I);
 891       delete I;
 892     } else {
 893       for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
 894            UI != UE; ++UI)
 895         assert(isa<ValueHandle>((Value*)*UI) &&"Uses of Instruction remain!!!");
 896     }
 897   }
 898 }
 899
 900
 901 ValueHandle::ValueHandle(ValueMapCache &VMC, Value *V)
 902   : Instruction(Type::VoidTy, UserOp1, ""), Cache(VMC) {
 903 #ifdef DEBUG_EXPR_CONVERT
 904   //cerr << "VH AQUIRING: " << (void*)V << " " << V;
 905 #endif
 906   Operands.push_back(Use(V, this));
 907 }
 908
 909 static void RecursiveDelete(ValueMapCache &Cache, Instruction *I) {
 910   if (!I || !I->use_empty()) return;
 911
 912   assert(I->getParent() && "Inst not in basic block!");
 913
 914 #ifdef DEBUG_EXPR_CONVERT
 915   //cerr << "VH DELETING: " << (void*)I << " " << I;
 916 #endif
 917
 918   for (User::op_iterator OI = I->op_begin(), OE = I->op_end();
 919        OI != OE; ++OI) {
 920     Instruction *U = dyn_cast<Instruction>(*OI);
 921     if (U) {
 922       *OI = 0;
 923       RecursiveDelete(Cache, dyn_cast<Instruction>(U));
 924     }
 925   }
 926
 927   I->getParent()->getInstList().remove(I);
 928
 929   Cache.OperandsMapped.erase(I);
 930   Cache.ExprMap.erase(I);
 931   delete I;
 932 }
 933
 934 ValueHandle::~ValueHandle() {
 935   if (Operands[0]->use_size() == 1) {
 936     Value *V = Operands[0];
 937     Operands[0] = 0;   // Drop use!
 938
 939     // Now we just need to remove the old instruction so we don't get infinite
 940     // loops.  Note that we cannot use DCE because DCE won't remove a store
 941     // instruction, for example.
 942     //
 943     RecursiveDelete(Cache, dyn_cast<Instruction>(V));
 944   } else {
 945 #ifdef DEBUG_EXPR_CONVERT
 946     //cerr << "VH RELEASING: " << (void*)Operands[0].get() << " " << Operands[0]->use_size() << " " << Operands[0];
 947 #endif
 948   }
 949 }