lib/Transforms/ExprTypeConvert.cpp

   1 //===- ExprTypeConvert.cpp - Code to change an LLVM Expr Type -------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the part of level raising that checks to see if it is
  11 // possible to coerce an entire expression tree into a different type.  If
  12 // convertible, other routines from this file will do the conversion.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "TransformInternals.h"
  17 #include "llvm/Constants.h"
  18 #include "llvm/Instructions.h"
  19 #include "llvm/ADT/STLExtras.h"
  20 #include "llvm/Support/Debug.h"
  21 #include <algorithm>
  22 using namespace llvm;
  23
  24 static bool OperandConvertibleToType(User *U, Value *V, const Type *Ty,
  25                                      ValueTypeCache &ConvertedTypes,
  26                                      const TargetData &TD);
  27
  28 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
  29                                  ValueMapCache &VMC, const TargetData &TD);
  30
  31
  32 // ExpressionConvertibleToType - Return true if it is possible
  33 bool llvm::ExpressionConvertibleToType(Value *V, const Type *Ty,
  34                                  ValueTypeCache &CTMap, const TargetData &TD) {
  35   // Expression type must be holdable in a register.
  36   if (!Ty->isFirstClassType())
  37     return false;
  38
  39   ValueTypeCache::iterator CTMI = CTMap.find(V);
  40   if (CTMI != CTMap.end()) return CTMI->second == Ty;
  41
  42   // If it's a constant... all constants can be converted to a different
  43   // type.
  44   //
  45   if (isa<Constant>(V) && !isa<GlobalValue>(V))
  46     return true;
  47
  48   CTMap[V] = Ty;
  49   if (V->getType() == Ty) return true;  // Expression already correct type!
  50
  51   Instruction *I = dyn_cast<Instruction>(V);
  52   if (I == 0) return false;              // Otherwise, we can't convert!
  53
  54   switch (I->getOpcode()) {
  55   case Instruction::BitCast:
  56     if (!cast<BitCastInst>(I)->isLosslessCast())
  57       return false;
  58     // We do not allow conversion of a cast that casts from a ptr to array
  59     // of X to a *X.  For example: cast [4 x %List *] * %val to %List * *
  60     //
  61     if (const PointerType *SPT =
  62         dyn_cast<PointerType>(I->getOperand(0)->getType()))
  63       if (const PointerType *DPT = dyn_cast<PointerType>(I->getType()))
  64         if (const ArrayType *AT = dyn_cast<ArrayType>(SPT->getElementType()))
  65           if (AT->getElementType() == DPT->getElementType())
  66             return false;
  67     // Otherwise it is a lossless cast and we can allow it
  68     break;
  69
  70   case Instruction::Add:
  71   case Instruction::Sub:
  72     if (!Ty->isInteger() && !Ty->isFloatingPoint()) return false;
  73     if (!ExpressionConvertibleToType(I->getOperand(0), Ty, CTMap, TD) ||
  74         !ExpressionConvertibleToType(I->getOperand(1), Ty, CTMap, TD))
  75       return false;
  76     break;
  77   case Instruction::LShr:
  78   case Instruction::AShr:
  79     if (!Ty->isInteger()) return false;
  80     if (!ExpressionConvertibleToType(I->getOperand(0), Ty, CTMap, TD))
  81       return false;
  82     break;
  83   case Instruction::Shl:
  84     if (!Ty->isInteger()) return false;
  85     if (!ExpressionConvertibleToType(I->getOperand(0), Ty, CTMap, TD))
  86       return false;
  87     break;
  88
  89   case Instruction::Load: {
  90     LoadInst *LI = cast<LoadInst>(I);
  91     if (!ExpressionConvertibleToType(LI->getPointerOperand(),
  92                                      PointerType::get(Ty), CTMap, TD))
  93       return false;
  94     break;
  95   }
  96   case Instruction::PHI: {
  97     PHINode *PN = cast<PHINode>(I);
  98     // Be conservative if we find a giant PHI node.
  99     if (PN->getNumIncomingValues() > 32) return false;
 100
 101     for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i)
 102       if (!ExpressionConvertibleToType(PN->getIncomingValue(i), Ty, CTMap, TD))
 103         return false;
 104     break;
 105   }
 106
 107   case Instruction::GetElementPtr: {
 108     // GetElementPtr's are directly convertible to a pointer type if they have
 109     // a number of zeros at the end.  Because removing these values does not
 110     // change the logical offset of the GEP, it is okay and fair to remove them.
 111     // This can change this:
 112     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 113     //   %t2 = cast %List * * %t1 to %List *
 114     // into
 115     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 116     //
 117     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 118     const PointerType *PTy = dyn_cast<PointerType>(Ty);
 119     if (!PTy) return false;  // GEP must always return a pointer...
 120     const Type *PVTy = PTy->getElementType();
 121
 122     // Check to see if there are zero elements that we can remove from the
 123     // index array.  If there are, check to see if removing them causes us to
 124     // get to the right type...
 125     //
 126     std::vector<Value*> Indices(GEP->idx_begin(), GEP->idx_end());
 127     const Type *BaseType = GEP->getPointerOperand()->getType();
 128     const Type *ElTy = 0;
 129
 130     while (!Indices.empty() &&
 131            Indices.back() == Constant::getNullValue(Indices.back()->getType())){
 132       Indices.pop_back();
 133       ElTy = GetElementPtrInst::getIndexedType(BaseType, Indices, true);
 134       if (ElTy == PVTy)
 135         break;  // Found a match!!
 136       ElTy = 0;
 137     }
 138
 139     if (ElTy) break;   // Found a number of zeros we can strip off!
 140
 141     // Otherwise, it could be that we have something like this:
 142     //     getelementptr [[sbyte] *] * %reg115, long %reg138    ; [sbyte]**
 143     // and want to convert it into something like this:
 144     //     getelemenptr [[int] *] * %reg115, long %reg138      ; [int]**
 145     //
 146     if (GEP->getNumOperands() == 2 &&
 147         PTy->getElementType()->isSized() &&
 148         TD.getTypeSize(PTy->getElementType()) ==
 149         TD.getTypeSize(GEP->getType()->getElementType())) {
 150       const PointerType *NewSrcTy = PointerType::get(PVTy);
 151       if (!ExpressionConvertibleToType(I->getOperand(0), NewSrcTy, CTMap, TD))
 152         return false;
 153       break;
 154     }
 155
 156     return false;   // No match, maybe next time.
 157   }
 158
 159   case Instruction::Call: {
 160     if (isa<Function>(I->getOperand(0)))
 161       return false;  // Don't even try to change direct calls.
 162
 163     // If this is a function pointer, we can convert the return type if we can
 164     // convert the source function pointer.
 165     //
 166     const PointerType *PT = cast<PointerType>(I->getOperand(0)->getType());
 167     const FunctionType *FT = cast<FunctionType>(PT->getElementType());
 168     std::vector<const Type *> ArgTys(FT->param_begin(), FT->param_end());
 169     const FunctionType *NewTy =
 170       FunctionType::get(Ty, ArgTys, FT->isVarArg());
 171     if (!ExpressionConvertibleToType(I->getOperand(0),
 172                                      PointerType::get(NewTy), CTMap, TD))
 173       return false;
 174     break;
 175   }
 176   default:
 177     return false;
 178   }
 179
 180   // Expressions are only convertible if all of the users of the expression can
 181   // have this value converted.  This makes use of the map to avoid infinite
 182   // recursion.
 183   //
 184   for (Value::use_iterator It = I->use_begin(), E = I->use_end(); It != E; ++It)
 185     if (!OperandConvertibleToType(*It, I, Ty, CTMap, TD))
 186       return false;
 187
 188   return true;
 189 }
 190
 191
 192 Value *llvm::ConvertExpressionToType(Value *V, const Type *Ty,
 193                                      ValueMapCache &VMC, const TargetData &TD) {
 194   if (V->getType() == Ty) return V;  // Already where we need to be?
 195
 196   ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(V);
 197   if (VMCI != VMC.ExprMap.end()) {
 198     assert(VMCI->second->getType() == Ty);
 199
 200     if (Instruction *I = dyn_cast<Instruction>(V))
 201       ValueHandle IHandle(VMC, I);  // Remove I if it is unused now!
 202
 203     return VMCI->second;
 204   }
 205
 206   DOUT << "CETT: " << (void*)V << " " << *V;
 207
 208   Instruction *I = dyn_cast<Instruction>(V);
 209   if (I == 0) {
 210     Constant *CPV = cast<Constant>(V);
 211     // Constants are converted by constant folding the cast that is required.
 212     // We assume here that all casts are implemented for constant prop.
 213     // FIXME: This seems to work, but it is unclear why ZEXT is always the
 214     // right choice here.
 215     Instruction::CastOps opcode = CastInst::getCastOpcode(CPV, false, Ty,false);
 216     Value *Result = ConstantExpr::getCast(opcode, CPV, Ty);
 217     // Add the instruction to the expression map
 218     //VMC.ExprMap[V] = Result;
 219     return Result;
 220   }
 221
 222
 223   BasicBlock *BB = I->getParent();
 224   std::string Name = I->getName();  if (!Name.empty()) I->setName("");
 225   Instruction *Res;     // Result of conversion
 226
 227   ValueHandle IHandle(VMC, I);  // Prevent I from being removed!
 228
 229   Constant *Dummy = Constant::getNullValue(Ty);
 230
 231   switch (I->getOpcode()) {
 232   case Instruction::BitCast: {
 233     assert(VMC.NewCasts.count(ValueHandle(VMC, I)) == 0);
 234     Instruction::CastOps opcode = CastInst::getCastOpcode(I->getOperand(0),
 235         false, Ty, false);
 236     Res = CastInst::create(opcode, I->getOperand(0), Ty, Name);
 237     VMC.NewCasts.insert(ValueHandle(VMC, Res));
 238     break;
 239   }
 240
 241   case Instruction::Add:
 242   case Instruction::Sub:
 243     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
 244                                  Dummy, Dummy, Name);
 245     VMC.ExprMap[I] = Res;   // Add node to expression eagerly
 246
 247     Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC, TD));
 248     Res->setOperand(1, ConvertExpressionToType(I->getOperand(1), Ty, VMC, TD));
 249     break;
 250
 251   case Instruction::Shl:
 252   case Instruction::LShr:
 253   case Instruction::AShr:
 254     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), Dummy,
 255                         I->getOperand(1), Name);
 256     VMC.ExprMap[I] = Res;
 257     Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC, TD));
 258     break;
 259
 260   case Instruction::Load: {
 261     LoadInst *LI = cast<LoadInst>(I);
 262
 263     Res = new LoadInst(Constant::getNullValue(PointerType::get(Ty)), Name);
 264     VMC.ExprMap[I] = Res;
 265     Res->setOperand(0, ConvertExpressionToType(LI->getPointerOperand(),
 266                                                PointerType::get(Ty), VMC, TD));
 267     assert(Res->getOperand(0)->getType() == PointerType::get(Ty));
 268     assert(Ty == Res->getType());
 269     assert(Res->getType()->isFirstClassType() && "Load of structure or array!");
 270     break;
 271   }
 272
 273   case Instruction::PHI: {
 274     PHINode *OldPN = cast<PHINode>(I);
 275     PHINode *NewPN = new PHINode(Ty, Name);
 276
 277     VMC.ExprMap[I] = NewPN;   // Add node to expression eagerly
 278     while (OldPN->getNumOperands()) {
 279       BasicBlock *BB = OldPN->getIncomingBlock(0);
 280       Value *OldVal = OldPN->getIncomingValue(0);
 281       ValueHandle OldValHandle(VMC, OldVal);
 282       OldPN->removeIncomingValue(BB, false);
 283       Value *V = ConvertExpressionToType(OldVal, Ty, VMC, TD);
 284       NewPN->addIncoming(V, BB);
 285     }
 286     Res = NewPN;
 287     break;
 288   }
 289
 290   case Instruction::GetElementPtr: {
 291     // GetElementPtr's are directly convertible to a pointer type if they have
 292     // a number of zeros at the end.  Because removing these values does not
 293     // change the logical offset of the GEP, it is okay and fair to remove them.
 294     // This can change this:
 295     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 296     //   %t2 = cast %List * * %t1 to %List *
 297     // into
 298     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 299     //
 300     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 301
 302     // Check to see if there are zero elements that we can remove from the
 303     // index array.  If there are, check to see if removing them causes us to
 304     // get to the right type...
 305     //
 306     std::vector<Value*> Indices(GEP->idx_begin(), GEP->idx_end());
 307     const Type *BaseType = GEP->getPointerOperand()->getType();
 308     const Type *PVTy = cast<PointerType>(Ty)->getElementType();
 309     Res = 0;
 310     while (!Indices.empty() &&
 311            Indices.back() == Constant::getNullValue(Indices.back()->getType())){
 312       Indices.pop_back();
 313       if (GetElementPtrInst::getIndexedType(BaseType, Indices, true) == PVTy) {
 314         if (Indices.size() == 0)
 315           // We want to no-op cast this so use BitCast
 316           Res = new BitCastInst(GEP->getPointerOperand(), BaseType);
 317         else
 318           Res = new GetElementPtrInst(GEP->getPointerOperand(), Indices, Name);
 319         break;
 320       }
 321     }
 322
 323     // Otherwise, it could be that we have something like this:
 324     //     getelementptr [[sbyte] *] * %reg115, uint %reg138    ; [sbyte]**
 325     // and want to convert it into something like this:
 326     //     getelemenptr [[int] *] * %reg115, uint %reg138      ; [int]**
 327     //
 328     if (Res == 0) {
 329       const PointerType *NewSrcTy = PointerType::get(PVTy);
 330       std::vector<Value*> Indices(GEP->idx_begin(), GEP->idx_end());
 331       Res = new GetElementPtrInst(Constant::getNullValue(NewSrcTy),
 332                                   Indices, Name);
 333       VMC.ExprMap[I] = Res;
 334       Res->setOperand(0, ConvertExpressionToType(I->getOperand(0),
 335                                                  NewSrcTy, VMC, TD));
 336     }
 337
 338
 339     assert(Res && "Didn't find match!");
 340     break;
 341   }
 342
 343   case Instruction::Call: {
 344     assert(!isa<Function>(I->getOperand(0)));
 345
 346     // If this is a function pointer, we can convert the return type if we can
 347     // convert the source function pointer.
 348     //
 349     const PointerType *PT = cast<PointerType>(I->getOperand(0)->getType());
 350     const FunctionType *FT = cast<FunctionType>(PT->getElementType());
 351     std::vector<const Type *> ArgTys(FT->param_begin(), FT->param_end());
 352     const FunctionType *NewTy =
 353       FunctionType::get(Ty, ArgTys, FT->isVarArg());
 354     const PointerType *NewPTy = PointerType::get(NewTy);
 355     if (Ty == Type::VoidTy)
 356       Name = "";  // Make sure not to name calls that now return void!
 357
 358     Res = new CallInst(Constant::getNullValue(NewPTy),
 359                        std::vector<Value*>(I->op_begin()+1, I->op_end()),
 360                        Name);
 361     if (cast<CallInst>(I)->isTailCall())
 362       cast<CallInst>(Res)->setTailCall();
 363     cast<CallInst>(Res)->setCallingConv(cast<CallInst>(I)->getCallingConv());
 364     VMC.ExprMap[I] = Res;
 365     Res->setOperand(0, ConvertExpressionToType(I->getOperand(0),NewPTy,VMC,TD));
 366     break;
 367   }
 368   default:
 369     assert(0 && "Expression convertible, but don't know how to convert?");
 370     return 0;
 371   }
 372
 373   assert(Res->getType() == Ty && "Didn't convert expr to correct type!");
 374
 375   BB->getInstList().insert(I, Res);
 376
 377   // Add the instruction to the expression map
 378   VMC.ExprMap[I] = Res;
 379
 380
 381   //// WTF is this code!  FIXME: remove this.
 382   unsigned NumUses = I->getNumUses();
 383   for (unsigned It = 0; It < NumUses; ) {
 384     unsigned OldSize = NumUses;
 385     Value::use_iterator UI = I->use_begin();
 386     std::advance(UI, It);
 387     ConvertOperandToType(*UI, I, Res, VMC, TD);
 388     NumUses = I->getNumUses();
 389     if (NumUses == OldSize) ++It;
 390   }
 391
 392   DOUT << "ExpIn: " << (void*)I << " " << *I
 393        << "ExpOut: " << (void*)Res << " " << *Res;
 394
 395   return Res;
 396 }
 397
 398
 399
 400 // ValueConvertibleToType - Return true if it is possible
 401 bool llvm::ValueConvertibleToType(Value *V, const Type *Ty,
 402                                   ValueTypeCache &ConvertedTypes,
 403                                   const TargetData &TD) {
 404   ValueTypeCache::iterator I = ConvertedTypes.find(V);
 405   if (I != ConvertedTypes.end()) return I->second == Ty;
 406   ConvertedTypes[V] = Ty;
 407
 408   // It is safe to convert the specified value to the specified type IFF all of
 409   // the uses of the value can be converted to accept the new typed value.
 410   //
 411   if (V->getType() != Ty) {
 412     for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I)
 413       if (!OperandConvertibleToType(*I, V, Ty, ConvertedTypes, TD))
 414         return false;
 415   }
 416
 417   return true;
 418 }
 419
 420 // OperandConvertibleToType - Return true if it is possible to convert operand
 421 // V of User (instruction) U to the specified type.  This is true iff it is
 422 // possible to change the specified instruction to accept this.  CTMap is a map
 423 // of converted types, so that circular definitions will see the future type of
 424 // the expression, not the static current type.
 425 //
 426 static bool OperandConvertibleToType(User *U, Value *V, const Type *Ty,
 427                                      ValueTypeCache &CTMap,
 428                                      const TargetData &TD) {
 429   //  if (V->getType() == Ty) return true;   // Operand already the right type?
 430
 431   // Expression type must be holdable in a register.
 432   if (!Ty->isFirstClassType())
 433     return false;
 434
 435   Instruction *I = dyn_cast<Instruction>(U);
 436   if (I == 0) return false;              // We can't convert non-instructions!
 437
 438   switch (I->getOpcode()) {
 439   case Instruction::BitCast:
 440     assert(I->getOperand(0) == V);
 441     // We can convert the expr if the cast destination type is losslessly
 442     // convertible to the requested type.  Also, do not change a cast that
 443     // is a noop cast.  For all intents and purposes it should be eliminated.
 444     if (!cast<BitCastInst>(I)->isLosslessCast() ||
 445         I->getType() == I->getOperand(0)->getType())
 446       return false;
 447
 448     // We also do not allow conversion of a cast that casts from a ptr to array
 449     // of X to a *X.  For example: cast [4 x %List *] * %val to %List * *
 450     //
 451     if (const PointerType *SPT =
 452         dyn_cast<PointerType>(I->getOperand(0)->getType()))
 453       if (const PointerType *DPT = dyn_cast<PointerType>(I->getType()))
 454         if (const ArrayType *AT = dyn_cast<ArrayType>(SPT->getElementType()))
 455           if (AT->getElementType() == DPT->getElementType())
 456             return false;
 457     return true;
 458
 459   case Instruction::Add:
 460   case Instruction::Sub: {
 461     if (!Ty->isInteger() && !Ty->isFloatingPoint()) return false;
 462
 463     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
 464     return ValueConvertibleToType(I, Ty, CTMap, TD) &&
 465            ExpressionConvertibleToType(OtherOp, Ty, CTMap, TD);
 466   }
 467   case Instruction::ICmp: {
 468     if (cast<ICmpInst>(I)->getPredicate() == ICmpInst::ICMP_EQ ||
 469         cast<ICmpInst>(I)->getPredicate() == ICmpInst::ICMP_NE) {
 470       Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
 471       return ExpressionConvertibleToType(OtherOp, Ty, CTMap, TD);
 472     }
 473     return false;
 474   }
 475   case Instruction::LShr:
 476   case Instruction::AShr:
 477   case Instruction::Shl:
 478     if (I->getOperand(1) == V) return false;  // Cannot change shift amount type
 479     if (!Ty->isInteger()) return false;
 480     return ValueConvertibleToType(I, Ty, CTMap, TD);
 481
 482   case Instruction::Free:
 483     assert(I->getOperand(0) == V);
 484     return isa<PointerType>(Ty);    // Free can free any pointer type!
 485
 486   case Instruction::Load:
 487     // Cannot convert the types of any subscripts...
 488     if (I->getOperand(0) != V) return false;
 489
 490     if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
 491       LoadInst *LI = cast<LoadInst>(I);
 492
 493       const Type *LoadedTy = PT->getElementType();
 494
 495       // They could be loading the first element of a composite type...
 496       if (const CompositeType *CT = dyn_cast<CompositeType>(LoadedTy)) {
 497         unsigned Offset = 0;     // No offset, get first leaf.
 498         std::vector<Value*> Indices;  // Discarded...
 499         LoadedTy = getStructOffsetType(CT, Offset, Indices, TD, false);
 500         assert(Offset == 0 && "Offset changed from zero???");
 501       }
 502
 503       if (!LoadedTy->isFirstClassType())
 504         return false;
 505
 506       if (TD.getTypeSize(LoadedTy) != TD.getTypeSize(LI->getType()))
 507         return false;
 508
 509       return ValueConvertibleToType(LI, LoadedTy, CTMap, TD);
 510     }
 511     return false;
 512
 513   case Instruction::Store: {
 514     if (V == I->getOperand(0)) {
 515       ValueTypeCache::iterator CTMI = CTMap.find(I->getOperand(1));
 516       if (CTMI != CTMap.end()) {   // Operand #1 is in the table already?
 517         // If so, check to see if it's Ty*, or, more importantly, if it is a
 518         // pointer to a structure where the first element is a Ty... this code
 519         // is necessary because we might be trying to change the source and
 520         // destination type of the store (they might be related) and the dest
 521         // pointer type might be a pointer to structure.  Below we allow pointer
 522         // to structures where the 0th element is compatible with the value,
 523         // now we have to support the symmetrical part of this.
 524         //
 525         const Type *ElTy = cast<PointerType>(CTMI->second)->getElementType();
 526
 527         // Already a pointer to what we want?  Trivially accept...
 528         if (ElTy == Ty) return true;
 529
 530         // Tricky case now, if the destination is a pointer to structure,
 531         // obviously the source is not allowed to be a structure (cannot copy
 532         // a whole structure at a time), so the level raiser must be trying to
 533         // store into the first field.  Check for this and allow it now:
 534         //
 535         if (isa<StructType>(ElTy)) {
 536           unsigned Offset = 0;
 537           std::vector<Value*> Indices;
 538           ElTy = getStructOffsetType(ElTy, Offset, Indices, TD, false);
 539           assert(Offset == 0 && "Offset changed!");
 540           if (ElTy == 0)    // Element at offset zero in struct doesn't exist!
 541             return false;   // Can only happen for {}*
 542
 543           if (ElTy == Ty)   // Looks like the 0th element of structure is
 544             return true;    // compatible!  Accept now!
 545
 546           // Otherwise we know that we can't work, so just stop trying now.
 547           return false;
 548         }
 549       }
 550
 551       // Can convert the store if we can convert the pointer operand to match
 552       // the new  value type...
 553       return ExpressionConvertibleToType(I->getOperand(1), PointerType::get(Ty),
 554                                          CTMap, TD);
 555     } else if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
 556       const Type *ElTy = PT->getElementType();
 557       assert(V == I->getOperand(1));
 558
 559       if (isa<StructType>(ElTy)) {
 560         // We can change the destination pointer if we can store our first
 561         // argument into the first element of the structure...
 562         //
 563         unsigned Offset = 0;
 564         std::vector<Value*> Indices;
 565         ElTy = getStructOffsetType(ElTy, Offset, Indices, TD, false);
 566         assert(Offset == 0 && "Offset changed!");
 567         if (ElTy == 0)    // Element at offset zero in struct doesn't exist!
 568           return false;   // Can only happen for {}*
 569       }
 570
 571       // Must move the same amount of data...
 572       if (!ElTy->isSized() ||
 573           TD.getTypeSize(ElTy) != TD.getTypeSize(I->getOperand(0)->getType()))
 574         return false;
 575
 576       // Can convert store if the incoming value is convertible and if the
 577       // result will preserve semantics...
 578       const Type *Op0Ty = I->getOperand(0)->getType();
 579       if (Op0Ty->isInteger() == ElTy->isInteger() &&
 580           Op0Ty->isFloatingPoint() == ElTy->isFloatingPoint())
 581         return ExpressionConvertibleToType(I->getOperand(0), ElTy, CTMap, TD);
 582     }
 583     return false;
 584   }
 585
 586   case Instruction::PHI: {
 587     PHINode *PN = cast<PHINode>(I);
 588     // Be conservative if we find a giant PHI node.
 589     if (PN->getNumIncomingValues() > 32) return false;
 590
 591     for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i)
 592       if (!ExpressionConvertibleToType(PN->getIncomingValue(i), Ty, CTMap, TD))
 593         return false;
 594     return ValueConvertibleToType(PN, Ty, CTMap, TD);
 595   }
 596
 597   case Instruction::Call: {
 598     User::op_iterator OI = std::find(I->op_begin(), I->op_end(), V);
 599     assert (OI != I->op_end() && "Not using value!");
 600     unsigned OpNum = OI - I->op_begin();
 601
 602     // Are we trying to change the function pointer value to a new type?
 603     if (OpNum == 0) {
 604       const PointerType *PTy = dyn_cast<PointerType>(Ty);
 605       if (PTy == 0) return false;  // Can't convert to a non-pointer type...
 606       const FunctionType *FTy = dyn_cast<FunctionType>(PTy->getElementType());
 607       if (FTy == 0) return false;  // Can't convert to a non ptr to function...
 608
 609       // Do not allow converting to a call where all of the operands are ...'s
 610       if (FTy->getNumParams() == 0 && FTy->isVarArg())
 611         return false;              // Do not permit this conversion!
 612
 613       // Perform sanity checks to make sure that new function type has the
 614       // correct number of arguments...
 615       //
 616       unsigned NumArgs = I->getNumOperands()-1;  // Don't include function ptr
 617
 618       // Cannot convert to a type that requires more fixed arguments than
 619       // the call provides...
 620       //
 621       if (NumArgs < FTy->getNumParams()) return false;
 622
 623       // Unless this is a vararg function type, we cannot provide more arguments
 624       // than are desired...
 625       //
 626       if (!FTy->isVarArg() && NumArgs > FTy->getNumParams())
 627         return false;
 628
 629       // Okay, at this point, we know that the call and the function type match
 630       // number of arguments.  Now we see if we can convert the arguments
 631       // themselves.  Note that we do not require operands to be convertible,
 632       // we can insert casts if they are convertible but not compatible.  The
 633       // reason for this is that we prefer to have resolved functions but casted
 634       // arguments if possible.
 635       //
 636       for (unsigned i = 0, NA = FTy->getNumParams(); i < NA; ++i)
 637         if (FTy->getParamType(i) != I->getOperand(i+1)->getType())
 638           return false;   // Operands must have compatible types!
 639
 640       // Okay, at this point, we know that all of the arguments can be
 641       // converted.  We succeed if we can change the return type if
 642       // necessary...
 643       //
 644       return ValueConvertibleToType(I, FTy->getReturnType(), CTMap, TD);
 645     }
 646
 647     const PointerType *MPtr = cast<PointerType>(I->getOperand(0)->getType());
 648     const FunctionType *FTy = cast<FunctionType>(MPtr->getElementType());
 649     if (!FTy->isVarArg()) return false;
 650
 651     if ((OpNum-1) < FTy->getNumParams())
 652       return false;  // It's not in the varargs section...
 653
 654     // If we get this far, we know the value is in the varargs section of the
 655     // function!  We can convert if we don't reinterpret the value...
 656     //
 657     return isa<PointerType>(Ty) && isa<PointerType>(V->getType());
 658   }
 659   }
 660   return false;
 661 }
 662
 663
 664 void llvm::ConvertValueToNewType(Value *V, Value *NewVal, ValueMapCache &VMC,
 665                                  const TargetData &TD) {
 666   ValueHandle VH(VMC, V);
 667
 668   // FIXME: This is horrible!
 669   unsigned NumUses = V->getNumUses();
 670   for (unsigned It = 0; It < NumUses; ) {
 671     unsigned OldSize = NumUses;
 672     Value::use_iterator UI = V->use_begin();
 673     std::advance(UI, It);
 674     ConvertOperandToType(*UI, V, NewVal, VMC, TD);
 675     NumUses = V->getNumUses();
 676     if (NumUses == OldSize) ++It;
 677   }
 678 }
 679
 680
 681
 682 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
 683                                  ValueMapCache &VMC, const TargetData &TD) {
 684   if (isa<ValueHandle>(U)) return;  // Valuehandles don't let go of operands...
 685
 686   if (VMC.OperandsMapped.count(U)) return;
 687   VMC.OperandsMapped.insert(U);
 688
 689   ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(U);
 690   if (VMCI != VMC.ExprMap.end())
 691     return;
 692
 693
 694   Instruction *I = cast<Instruction>(U);  // Only Instructions convertible
 695
 696   BasicBlock *BB = I->getParent();
 697   assert(BB != 0 && "Instruction not embedded in basic block!");
 698   std::string Name = I->getName();
 699   I->setName("");
 700   Instruction *Res;     // Result of conversion
 701
 702   //cerr << endl << endl << "Type:\t" << Ty << "\nInst: " << I
 703   //     << "BB Before: " << BB << endl;
 704
 705   // Prevent I from being removed...
 706   ValueHandle IHandle(VMC, I);
 707
 708   const Type *NewTy = NewVal->getType();
 709   Constant *Dummy = (NewTy != Type::VoidTy) ?
 710                   Constant::getNullValue(NewTy) : 0;
 711
 712   switch (I->getOpcode()) {
 713   case Instruction::BitCast: {
 714     Instruction::CastOps opcode = CastInst::getCastOpcode(NewVal, false,
 715                                                           I->getType(), false);
 716     Res = CastInst::create(opcode, NewVal, I->getType(), Name);
 717     break;
 718   }
 719
 720   case Instruction::Add:
 721   case Instruction::Sub: {
 722     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
 723                                  Dummy, Dummy, Name);
 724     VMC.ExprMap[I] = Res;   // Add node to expression eagerly
 725
 726     unsigned OtherIdx = (OldVal == I->getOperand(0)) ? 1 : 0;
 727     Value *OtherOp    = I->getOperand(OtherIdx);
 728     Res->setOperand(!OtherIdx, NewVal);
 729     Value *NewOther   = ConvertExpressionToType(OtherOp, NewTy, VMC, TD);
 730     Res->setOperand(OtherIdx, NewOther);
 731     break;
 732   }
 733   case Instruction::ICmp: {
 734     ICmpInst::Predicate pred = cast<ICmpInst>(I)->getPredicate();
 735     if (pred == ICmpInst::ICMP_EQ || pred == ICmpInst::ICMP_NE) {
 736       Res = new ICmpInst(pred, Dummy, Dummy, Name);
 737       VMC.ExprMap[I] = Res;  // Add node to expression eagerly
 738       unsigned OtherIdx = (OldVal == I->getOperand(0)) ? 1 : 0;
 739       Value *OtherOp    = I->getOperand(OtherIdx);
 740       Res->setOperand(!OtherIdx, NewVal);
 741       Value *NewOther   = ConvertExpressionToType(OtherOp, NewTy, VMC, TD);
 742       Res->setOperand(OtherIdx, NewOther);
 743     }
 744     break;
 745   }
 746   case Instruction::Shl:
 747   case Instruction::LShr:
 748   case Instruction::AShr:
 749     assert(I->getOperand(0) == OldVal);
 750     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), NewVal,
 751                         I->getOperand(1), Name);
 752     break;
 753
 754   case Instruction::Free:            // Free can free any pointer type!
 755     assert(I->getOperand(0) == OldVal);
 756     Res = new FreeInst(NewVal);
 757     break;
 758
 759
 760   case Instruction::Load: {
 761     assert(I->getOperand(0) == OldVal && isa<PointerType>(NewVal->getType()));
 762     const Type *LoadedTy =
 763       cast<PointerType>(NewVal->getType())->getElementType();
 764
 765     Value *Src = NewVal;
 766
 767     if (const CompositeType *CT = dyn_cast<CompositeType>(LoadedTy)) {
 768       std::vector<Value*> Indices;
 769       Indices.push_back(Constant::getNullValue(Type::Int32Ty));
 770
 771       unsigned Offset = 0;   // No offset, get first leaf.
 772       LoadedTy = getStructOffsetType(CT, Offset, Indices, TD, false);
 773       assert(LoadedTy->isFirstClassType());
 774
 775       if (Indices.size() != 1) {     // Do not generate load X, 0
 776         // Insert the GEP instruction before this load.
 777         Src = new GetElementPtrInst(Src, Indices, Name+".idx", I);
 778       }
 779     }
 780
 781     Res = new LoadInst(Src, Name);
 782     assert(Res->getType()->isFirstClassType() && "Load of structure or array!");
 783     break;
 784   }
 785
 786   case Instruction::Store: {
 787     if (I->getOperand(0) == OldVal) {  // Replace the source value
 788       // Check to see if operand #1 has already been converted...
 789       ValueMapCache::ExprMapTy::iterator VMCI =
 790         VMC.ExprMap.find(I->getOperand(1));
 791       if (VMCI != VMC.ExprMap.end()) {
 792         // Comments describing this stuff are in the OperandConvertibleToType
 793         // switch statement for Store...
 794         //
 795         const Type *ElTy =
 796           cast<PointerType>(VMCI->second->getType())->getElementType();
 797
 798         Value *SrcPtr = VMCI->second;
 799
 800         if (ElTy != NewTy) {
 801           std::vector<Value*> Indices;
 802           Indices.push_back(Constant::getNullValue(Type::Int32Ty));
 803
 804           unsigned Offset = 0;
 805           const Type *Ty = getStructOffsetType(ElTy, Offset, Indices, TD,false);
 806           assert(Offset == 0 && "Offset changed!");
 807           assert(NewTy == Ty && "Did not convert to correct type!");
 808
 809           // Insert the GEP instruction before this store.
 810           SrcPtr = new GetElementPtrInst(SrcPtr, Indices,
 811                                          SrcPtr->getName()+".idx", I);
 812         }
 813         Res = new StoreInst(NewVal, SrcPtr);
 814
 815         VMC.ExprMap[I] = Res;
 816       } else {
 817         // Otherwise, we haven't converted Operand #1 over yet...
 818         const PointerType *NewPT = PointerType::get(NewTy);
 819         Res = new StoreInst(NewVal, Constant::getNullValue(NewPT));
 820         VMC.ExprMap[I] = Res;
 821         Res->setOperand(1, ConvertExpressionToType(I->getOperand(1),
 822                                                    NewPT, VMC, TD));
 823       }
 824     } else {                           // Replace the source pointer
 825       const Type *ValTy = cast<PointerType>(NewTy)->getElementType();
 826
 827       Value *SrcPtr = NewVal;
 828
 829       if (isa<StructType>(ValTy)) {
 830         std::vector<Value*> Indices;
 831         Indices.push_back(Constant::getNullValue(Type::Int32Ty));
 832
 833         unsigned Offset = 0;
 834         ValTy = getStructOffsetType(ValTy, Offset, Indices, TD, false);
 835
 836         assert(Offset == 0 && ValTy);
 837
 838         // Insert the GEP instruction before this store.
 839         SrcPtr = new GetElementPtrInst(SrcPtr, Indices,
 840                                        SrcPtr->getName()+".idx", I);
 841       }
 842
 843       Res = new StoreInst(Constant::getNullValue(ValTy), SrcPtr);
 844       VMC.ExprMap[I] = Res;
 845       Res->setOperand(0, ConvertExpressionToType(I->getOperand(0),
 846                                                  ValTy, VMC, TD));
 847     }
 848     break;
 849   }
 850
 851   case Instruction::PHI: {
 852     PHINode *OldPN = cast<PHINode>(I);
 853     PHINode *NewPN = new PHINode(NewTy, Name);
 854     VMC.ExprMap[I] = NewPN;
 855
 856     while (OldPN->getNumOperands()) {
 857       BasicBlock *BB = OldPN->getIncomingBlock(0);
 858       Value *OldVal = OldPN->getIncomingValue(0);
 859       ValueHandle OldValHandle(VMC, OldVal);
 860       OldPN->removeIncomingValue(BB, false);
 861       Value *V = ConvertExpressionToType(OldVal, NewTy, VMC, TD);
 862       NewPN->addIncoming(V, BB);
 863     }
 864     Res = NewPN;
 865     break;
 866   }
 867
 868   case Instruction::Call: {
 869     Value *Meth = I->getOperand(0);
 870     std::vector<Value*> Params(I->op_begin()+1, I->op_end());
 871
 872     if (Meth == OldVal) {   // Changing the function pointer?
 873       const PointerType *NewPTy = cast<PointerType>(NewVal->getType());
 874       const FunctionType *NewTy = cast<FunctionType>(NewPTy->getElementType());
 875
 876       if (NewTy->getReturnType() == Type::VoidTy)
 877         Name = "";  // Make sure not to name a void call!
 878
 879       // Get an iterator to the call instruction so that we can insert casts for
 880       // operands if need be.  Note that we do not require operands to be
 881       // convertible, we can insert casts if they are convertible but not
 882       // compatible.  The reason for this is that we prefer to have resolved
 883       // functions but casted arguments if possible.
 884       //
 885       BasicBlock::iterator It = I;
 886
 887       // Convert over all of the call operands to their new types... but only
 888       // convert over the part that is not in the vararg section of the call.
 889       //
 890       for (unsigned i = 0; i != NewTy->getNumParams(); ++i)
 891         if (Params[i]->getType() != NewTy->getParamType(i)) {
 892           // Create a cast to convert it to the right type, we know that this
 893           // is a no-op cast...
 894           //
 895           Params[i] = new BitCastInst(Params[i], NewTy->getParamType(i),
 896                                    "callarg.cast." +
 897                                    Params[i]->getName(), It);
 898         }
 899       Meth = NewVal;  // Update call destination to new value
 900
 901     } else {                   // Changing an argument, must be in vararg area
 902       std::vector<Value*>::iterator OI =
 903         std::find(Params.begin(), Params.end(), OldVal);
 904       assert (OI != Params.end() && "Not using value!");
 905
 906       *OI = NewVal;
 907     }
 908
 909     Res = new CallInst(Meth, Params, Name);
 910     if (cast<CallInst>(I)->isTailCall())
 911       cast<CallInst>(Res)->setTailCall();
 912     cast<CallInst>(Res)->setCallingConv(cast<CallInst>(I)->getCallingConv());
 913     break;
 914   }
 915   default:
 916     assert(0 && "Expression convertible, but don't know how to convert?");
 917     return;
 918   }
 919
 920   // If the instruction was newly created, insert it into the instruction
 921   // stream.
 922   //
 923   BasicBlock::iterator It = I;
 924   assert(It != BB->end() && "Instruction not in own basic block??");
 925   BB->getInstList().insert(It, Res);   // Keep It pointing to old instruction
 926
 927   DOUT << "COT CREATED: "  << (void*)Res << " " << *Res
 928        << "In: " << (void*)I << " " << *I << "Out: " << (void*)Res
 929        << " " << *Res;
 930
 931   // Add the instruction to the expression map
 932   VMC.ExprMap[I] = Res;
 933
 934   if (I->getType() != Res->getType())
 935     ConvertValueToNewType(I, Res, VMC, TD);
 936   else {
 937     for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
 938          UI != E; )
 939       if (isa<ValueHandle>(*UI)) {
 940         ++UI;
 941       } else {
 942         Use &U = UI.getUse();
 943         ++UI;  // Do not invalidate UI.
 944         U.set(Res);
 945       }
 946   }
 947 }
 948
 949
 950 ValueHandle::ValueHandle(ValueMapCache &VMC, Value *V)
 951   : Instruction(Type::VoidTy, UserOp1, &Op, 1, ""), Op(V, this), Cache(VMC) {
 952   //DOUT << "VH AQUIRING: " << (void*)V << " " << V;
 953 }
 954
 955 ValueHandle::ValueHandle(const ValueHandle &VH)
 956   : Instruction(Type::VoidTy, UserOp1, &Op, 1, ""),
 957     Op(VH.Op, this), Cache(VH.Cache) {
 958   //DOUT << "VH AQUIRING: " << (void*)V << " " << V;
 959 }
 960
 961 static void RecursiveDelete(ValueMapCache &Cache, Instruction *I) {
 962   if (!I || !I->use_empty()) return;
 963
 964   assert(I->getParent() && "Inst not in basic block!");
 965
 966   //DOUT << "VH DELETING: " << (void*)I << " " << I;
 967
 968   for (User::op_iterator OI = I->op_begin(), OE = I->op_end();
 969        OI != OE; ++OI)
 970     if (Instruction *U = dyn_cast<Instruction>(OI)) {
 971       *OI = 0;
 972       RecursiveDelete(Cache, U);
 973     }
 974
 975   I->getParent()->getInstList().remove(I);
 976
 977   Cache.OperandsMapped.erase(I);
 978   Cache.ExprMap.erase(I);
 979   delete I;
 980 }
 981
 982 ValueHandle::~ValueHandle() {
 983   if (Op->hasOneUse()) {
 984     Value *V = Op;
 985     Op.set(0);   // Drop use!
 986
 987     // Now we just need to remove the old instruction so we don't get infinite
 988     // loops.  Note that we cannot use DCE because DCE won't remove a store
 989     // instruction, for example.
 990     //
 991     RecursiveDelete(Cache, dyn_cast<Instruction>(V));
 992   } else {
 993     //DOUT << "VH RELEASING: " << (void*)Operands[0].get() << " "
 994     //     << Operands[0]->getNumUses() << " " << Operands[0];
 995   }
 996 }