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
  45 // Peephole Malloc instructions: we take a look at the use chain of the
  46 // malloc instruction, and try to find out if the following conditions hold:
  47 //   1. The malloc is of the form: 'malloc [sbyte], uint <constant>'
  48 //   2. The only users of the malloc are cast & add instructions
  49 //   3. Of the cast instructions, there is only one destination pointer type
  50 //      [RTy] where the size of the pointed to object is equal to the number
  51 //      of bytes allocated.
  52 //
  53 // If these conditions hold, we convert the malloc to allocate an [RTy]
  54 // element.  TODO: This comment is out of date WRT arrays
  55 //
  56 static bool MallocConvertableToType(MallocInst *MI, const Type *Ty,
  57                                     ValueTypeCache &CTMap) {
  58   if (!MI->isArrayAllocation() ||            // No array allocation?
  59       !isa<PointerType>(Ty)) return false;   // Malloc always returns pointers
  60
  61   // Deal with the type to allocate, not the pointer type...
  62   Ty = cast<PointerType>(Ty)->getElementType();
  63   if (!Ty->isSized()) return false;      // Can only alloc something with a size
  64
  65   // Analyze the number of bytes allocated...
  66   analysis::ExprType Expr = analysis::ClassifyExpression(MI->getArraySize());
  67
  68   // Get information about the base datatype being allocated, before & after
  69   unsigned ReqTypeSize = TD.getTypeSize(Ty);
  70   unsigned OldTypeSize = TD.getTypeSize(MI->getType()->getElementType());
  71
  72   // Must have a scale or offset to analyze it...
  73   if (!Expr.Offset && !Expr.Scale) return false;
  74
  75   // Get the offset and scale of the allocation...
  76   int OffsetVal = Expr.Offset ? getConstantValue(Expr.Offset) : 0;
  77   int ScaleVal = Expr.Scale ? getConstantValue(Expr.Scale) : (Expr.Var ? 1 : 0);
  78   if (ScaleVal < 0 || OffsetVal < 0) {
  79     cerr << "malloc of a negative number???\n";
  80     return false;
  81   }
  82
  83   // The old type might not be of unit size, take old size into consideration
  84   // here...
  85   unsigned Offset = (unsigned)OffsetVal * OldTypeSize;
  86   unsigned Scale  = (unsigned)ScaleVal  * OldTypeSize;
  87
  88   // In order to be successful, both the scale and the offset must be a multiple
  89   // of the requested data type's size.
  90   //
  91   if (Offset/ReqTypeSize*ReqTypeSize != Offset ||
  92       Scale/ReqTypeSize*ReqTypeSize != Scale)
  93     return false;   // Nope.
  94
  95   return true;
  96 }
  97
  98 static Instruction *ConvertMallocToType(MallocInst *MI, const Type *Ty,
  99                                         const string &Name, ValueMapCache &VMC){
 100   BasicBlock *BB = MI->getParent();
 101   BasicBlock::iterator It = BB->end();
 102
 103   // Analyze the number of bytes allocated...
 104   analysis::ExprType Expr = analysis::ClassifyExpression(MI->getArraySize());
 105
 106   const PointerType *AllocTy = cast<PointerType>(Ty);
 107   const Type *ElType = AllocTy->getElementType();
 108
 109   unsigned DataSize = TD.getTypeSize(ElType);
 110   unsigned OldTypeSize = TD.getTypeSize(MI->getType()->getElementType());
 111
 112   // Get the offset and scale coefficients that we are allocating...
 113   int OffsetVal = (Expr.Offset ? getConstantValue(Expr.Offset) : 0);
 114   int ScaleVal = Expr.Scale ? getConstantValue(Expr.Scale) : (Expr.Var ? 1 : 0);
 115
 116   // The old type might not be of unit size, take old size into consideration
 117   // here...
 118   unsigned Offset = (unsigned)OffsetVal * OldTypeSize / DataSize;
 119   unsigned Scale  = (unsigned)ScaleVal  * OldTypeSize / DataSize;
 120
 121   // Locate the malloc instruction, because we may be inserting instructions
 122   It = find(BB->getInstList().begin(), BB->getInstList().end(), MI);
 123
 124   // If we have a scale, apply it first...
 125   if (Expr.Var) {
 126     // Expr.Var is not neccesarily unsigned right now, insert a cast now.
 127     if (Expr.Var->getType() != Type::UIntTy) {
 128       Instruction *CI = new CastInst(Expr.Var, Type::UIntTy);
 129       if (Expr.Var->hasName()) CI->setName(Expr.Var->getName()+"-uint");
 130       It = BB->getInstList().insert(It, CI)+1;
 131       Expr.Var = CI;
 132     }
 133
 134     if (Scale != 1) {
 135       Instruction *ScI =
 136         BinaryOperator::create(Instruction::Mul, Expr.Var,
 137                                ConstantUInt::get(Type::UIntTy, Scale));
 138       if (Expr.Var->hasName()) ScI->setName(Expr.Var->getName()+"-scl");
 139       It = BB->getInstList().insert(It, ScI)+1;
 140       Expr.Var = ScI;
 141     }
 142
 143   } else {
 144     // If we are not scaling anything, just make the offset be the "var"...
 145     Expr.Var = ConstantUInt::get(Type::UIntTy, Offset);
 146     Offset = 0; Scale = 1;
 147   }
 148
 149   // If we have an offset now, add it in...
 150   if (Offset != 0) {
 151     assert(Expr.Var && "Var must be nonnull by now!");
 152
 153     Instruction *AddI =
 154       BinaryOperator::create(Instruction::Add, Expr.Var,
 155                              ConstantUInt::get(Type::UIntTy, Offset));
 156     if (Expr.Var->hasName()) AddI->setName(Expr.Var->getName()+"-off");
 157     It = BB->getInstList().insert(It, AddI)+1;
 158     Expr.Var = AddI;
 159   }
 160
 161   Instruction *NewI = new MallocInst(AllocTy, Expr.Var, Name);
 162
 163   assert(AllocTy == Ty);
 164   return NewI;
 165 }
 166
 167
 168 // ExpressionConvertableToType - Return true if it is possible
 169 bool ExpressionConvertableToType(Value *V, const Type *Ty,
 170                                  ValueTypeCache &CTMap) {
 171   if (V->getType() == Ty) return true;  // Expression already correct type!
 172
 173   // Expression type must be holdable in a register.
 174   if (!Ty->isFirstClassType())
 175     return false;
 176
 177   ValueTypeCache::iterator CTMI = CTMap.find(V);
 178   if (CTMI != CTMap.end()) return CTMI->second == Ty;
 179
 180   CTMap[V] = Ty;
 181
 182   Instruction *I = dyn_cast<Instruction>(V);
 183   if (I == 0) {
 184     // It's not an instruction, check to see if it's a constant... all constants
 185     // can be converted to an equivalent value (except pointers, they can't be
 186     // const prop'd in general).  We just ask the constant propogator to see if
 187     // it can convert the value...
 188     //
 189     if (Constant *CPV = dyn_cast<Constant>(V))
 190       if (opt::ConstantFoldCastInstruction(CPV, Ty))
 191         return true;  // Don't worry about deallocating, it's a constant.
 192
 193     return false;              // Otherwise, we can't convert!
 194   }
 195
 196   switch (I->getOpcode()) {
 197   case Instruction::Cast:
 198     // We can convert the expr if the cast destination type is losslessly
 199     // convertable to the requested type.
 200     if (!Ty->isLosslesslyConvertableTo(I->getType())) return false;
 201 #if 1
 202     // We also do not allow conversion of a cast that casts from a ptr to array
 203     // of X to a *X.  For example: cast [4 x %List *] * %val to %List * *
 204     //
 205     if (PointerType *SPT = dyn_cast<PointerType>(I->getOperand(0)->getType()))
 206       if (PointerType *DPT = dyn_cast<PointerType>(I->getType()))
 207         if (ArrayType *AT = dyn_cast<ArrayType>(SPT->getElementType()))
 208           if (AT->getElementType() == DPT->getElementType())
 209             return false;
 210 #endif
 211     break;
 212
 213   case Instruction::Add:
 214   case Instruction::Sub:
 215     if (!ExpressionConvertableToType(I->getOperand(0), Ty, CTMap) ||
 216         !ExpressionConvertableToType(I->getOperand(1), Ty, CTMap))
 217       return false;
 218     break;
 219   case Instruction::Shr:
 220     if (Ty->isSigned() != V->getType()->isSigned()) return false;
 221     // FALL THROUGH
 222   case Instruction::Shl:
 223     if (!ExpressionConvertableToType(I->getOperand(0), Ty, CTMap))
 224       return false;
 225     break;
 226
 227   case Instruction::Load: {
 228     LoadInst *LI = cast<LoadInst>(I);
 229     if (LI->hasIndices() && !AllIndicesZero(LI)) {
 230       // We can't convert a load expression if it has indices... unless they are
 231       // all zero.
 232       return false;
 233     }
 234
 235     if (!ExpressionConvertableToType(LI->getPointerOperand(),
 236                                      PointerType::get(Ty), CTMap))
 237       return false;
 238     break;
 239   }
 240   case Instruction::PHINode: {
 241     PHINode *PN = cast<PHINode>(I);
 242     for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i)
 243       if (!ExpressionConvertableToType(PN->getIncomingValue(i), Ty, CTMap))
 244         return false;
 245     break;
 246   }
 247
 248   case Instruction::Malloc:
 249     if (!MallocConvertableToType(cast<MallocInst>(I), Ty, CTMap))
 250       return false;
 251     break;
 252
 253 #if 1
 254   case Instruction::GetElementPtr: {
 255     // GetElementPtr's are directly convertable to a pointer type if they have
 256     // a number of zeros at the end.  Because removing these values does not
 257     // change the logical offset of the GEP, it is okay and fair to remove them.
 258     // This can change this:
 259     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 260     //   %t2 = cast %List * * %t1 to %List *
 261     // into
 262     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 263     //
 264     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 265     const PointerType *PTy = dyn_cast<PointerType>(Ty);
 266     if (!PTy) return false;  // GEP must always return a pointer...
 267     const Type *PVTy = PTy->getElementType();
 268
 269     // Check to see if there are zero elements that we can remove from the
 270     // index array.  If there are, check to see if removing them causes us to
 271     // get to the right type...
 272     //
 273     vector<Value*> Indices = GEP->copyIndices();
 274     const Type *BaseType = GEP->getPointerOperand()->getType();
 275     const Type *ElTy = 0;
 276
 277     while (!Indices.empty() && isa<ConstantUInt>(Indices.back()) &&
 278            cast<ConstantUInt>(Indices.back())->getValue() == 0) {
 279       Indices.pop_back();
 280       ElTy = GetElementPtrInst::getIndexedType(BaseType, Indices, true);
 281       if (ElTy == PVTy)
 282         break;  // Found a match!!
 283       ElTy = 0;
 284     }
 285
 286     if (ElTy) break;   // Found a number of zeros we can strip off!
 287
 288     // Otherwise, we can convert a GEP from one form to the other iff the
 289     // current gep is of the form 'getelementptr sbyte*, unsigned N
 290     // and we could convert this to an appropriate GEP for the new type.
 291     //
 292     if (GEP->getNumOperands() == 2 &&
 293         GEP->getOperand(1)->getType() == Type::UIntTy &&
 294         GEP->getType() == PointerType::get(Type::SByteTy)) {
 295
 296       // Do not Check to see if our incoming pointer can be converted
 297       // to be a ptr to an array of the right type... because in more cases than
 298       // not, it is simply not analyzable because of pointer/array
 299       // discrepencies.  To fix this, we will insert a cast before the GEP.
 300       //
 301
 302       // Check to see if 'N' is an expression that can be converted to
 303       // the appropriate size... if so, allow it.
 304       //
 305       vector<Value*> Indices;
 306       const Type *ElTy = ConvertableToGEP(PTy, I->getOperand(1), Indices);
 307       if (ElTy) {
 308         assert(ElTy == PVTy && "Internal error, setup wrong!");
 309         if (!ExpressionConvertableToType(I->getOperand(0),
 310                                          PointerType::get(ElTy), CTMap))
 311           return false;  // Can't continue, ExConToTy might have polluted set!
 312         break;
 313       }
 314     }
 315
 316     // Otherwise, it could be that we have something like this:
 317     //     getelementptr [[sbyte] *] * %reg115, uint %reg138    ; [sbyte]**
 318     // and want to convert it into something like this:
 319     //     getelemenptr [[int] *] * %reg115, uint %reg138      ; [int]**
 320     //
 321     if (GEP->getNumOperands() == 2 &&
 322         GEP->getOperand(1)->getType() == Type::UIntTy &&
 323         TD.getTypeSize(PTy->getElementType()) ==
 324         TD.getTypeSize(GEP->getType()->getElementType())) {
 325       const PointerType *NewSrcTy = PointerType::get(PVTy);
 326       if (!ExpressionConvertableToType(I->getOperand(0), NewSrcTy, CTMap))
 327         return false;
 328       break;
 329     }
 330
 331     return false;   // No match, maybe next time.
 332   }
 333 #endif
 334
 335   default:
 336     return false;
 337   }
 338
 339   // Expressions are only convertable if all of the users of the expression can
 340   // have this value converted.  This makes use of the map to avoid infinite
 341   // recursion.
 342   //
 343   for (Value::use_iterator It = I->use_begin(), E = I->use_end(); It != E; ++It)
 344     if (!OperandConvertableToType(*It, I, Ty, CTMap))
 345       return false;
 346
 347   return true;
 348 }
 349
 350
 351 Value *ConvertExpressionToType(Value *V, const Type *Ty, ValueMapCache &VMC) {
 352   if (V->getType() == Ty) return V;  // Already where we need to be?
 353
 354   ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(V);
 355   if (VMCI != VMC.ExprMap.end()) {
 356     assert(VMCI->second->getType() == Ty);
 357     return VMCI->second;
 358   }
 359
 360 #ifdef DEBUG_EXPR_CONVERT
 361   cerr << "CETT: " << (void*)V << " " << V;
 362 #endif
 363
 364   Instruction *I = dyn_cast<Instruction>(V);
 365   if (I == 0)
 366     if (Constant *CPV = cast<Constant>(V)) {
 367       // Constants are converted by constant folding the cast that is required.
 368       // We assume here that all casts are implemented for constant prop.
 369       Value *Result = opt::ConstantFoldCastInstruction(CPV, Ty);
 370       assert(Result && "ConstantFoldCastInstruction Failed!!!");
 371       assert(Result->getType() == Ty && "Const prop of cast failed!");
 372
 373       // Add the instruction to the expression map
 374       VMC.ExprMap[V] = Result;
 375       return Result;
 376     }
 377
 378
 379   BasicBlock *BB = I->getParent();
 380   BasicBlock::InstListType &BIL = BB->getInstList();
 381   string Name = I->getName();  if (!Name.empty()) I->setName("");
 382   Instruction *Res;     // Result of conversion
 383
 384   ValueHandle IHandle(VMC, I);  // Prevent I from being removed!
 385
 386   Constant *Dummy = Constant::getNullConstant(Ty);
 387
 388   switch (I->getOpcode()) {
 389   case Instruction::Cast:
 390     Res = new CastInst(I->getOperand(0), Ty, Name);
 391     break;
 392
 393   case Instruction::Add:
 394   case Instruction::Sub:
 395     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
 396                                  Dummy, Dummy, Name);
 397     VMC.ExprMap[I] = Res;   // Add node to expression eagerly
 398
 399     Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC));
 400     Res->setOperand(1, ConvertExpressionToType(I->getOperand(1), Ty, VMC));
 401     break;
 402
 403   case Instruction::Shl:
 404   case Instruction::Shr:
 405     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), Dummy,
 406                         I->getOperand(1), Name);
 407     VMC.ExprMap[I] = Res;
 408     Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC));
 409     break;
 410
 411   case Instruction::Load: {
 412     LoadInst *LI = cast<LoadInst>(I);
 413     assert(!LI->hasIndices() || AllIndicesZero(LI));
 414
 415     Res = new LoadInst(Constant::getNullConstant(PointerType::get(Ty)), Name);
 416     VMC.ExprMap[I] = Res;
 417     Res->setOperand(0, ConvertExpressionToType(LI->getPointerOperand(),
 418                                                PointerType::get(Ty), VMC));
 419     assert(Res->getOperand(0)->getType() == PointerType::get(Ty));
 420     assert(Ty == Res->getType());
 421     assert(Res->getType()->isFirstClassType() && "Load of structure or array!");
 422     break;
 423   }
 424
 425   case Instruction::PHINode: {
 426     PHINode *OldPN = cast<PHINode>(I);
 427     PHINode *NewPN = new PHINode(Ty, Name);
 428
 429     VMC.ExprMap[I] = NewPN;   // Add node to expression eagerly
 430     while (OldPN->getNumOperands()) {
 431       BasicBlock *BB = OldPN->getIncomingBlock(0);
 432       Value *OldVal = OldPN->getIncomingValue(0);
 433       ValueHandle OldValHandle(VMC, OldVal);
 434       OldPN->removeIncomingValue(BB);
 435       Value *V = ConvertExpressionToType(OldVal, Ty, VMC);
 436       NewPN->addIncoming(V, BB);
 437     }
 438     Res = NewPN;
 439     break;
 440   }
 441
 442   case Instruction::Malloc: {
 443     Res = ConvertMallocToType(cast<MallocInst>(I), Ty, Name, VMC);
 444     break;
 445   }
 446
 447   case Instruction::GetElementPtr: {
 448     // GetElementPtr's are directly convertable to a pointer type if they have
 449     // a number of zeros at the end.  Because removing these values does not
 450     // change the logical offset of the GEP, it is okay and fair to remove them.
 451     // This can change this:
 452     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 453     //   %t2 = cast %List * * %t1 to %List *
 454     // into
 455     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 456     //
 457     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 458
 459     // Check to see if there are zero elements that we can remove from the
 460     // index array.  If there are, check to see if removing them causes us to
 461     // get to the right type...
 462     //
 463     vector<Value*> Indices = GEP->copyIndices();
 464     const Type *BaseType = GEP->getPointerOperand()->getType();
 465     const Type *PVTy = cast<PointerType>(Ty)->getElementType();
 466     Res = 0;
 467     while (!Indices.empty() && isa<ConstantUInt>(Indices.back()) &&
 468            cast<ConstantUInt>(Indices.back())->getValue() == 0) {
 469       Indices.pop_back();
 470       if (GetElementPtrInst::getIndexedType(BaseType, Indices, true) == PVTy) {
 471         if (Indices.size() == 0) {
 472           Res = new CastInst(GEP->getPointerOperand(), BaseType); // NOOP
 473         } else {
 474           Res = new GetElementPtrInst(GEP->getPointerOperand(), Indices, Name);
 475         }
 476         break;
 477       }
 478     }
 479
 480     if (Res == 0 && GEP->getNumOperands() == 2 &&
 481         GEP->getOperand(1)->getType() == Type::UIntTy &&
 482         GEP->getType() == PointerType::get(Type::SByteTy)) {
 483
 484       // Otherwise, we can convert a GEP from one form to the other iff the
 485       // current gep is of the form 'getelementptr [sbyte]*, unsigned N
 486       // and we could convert this to an appropriate GEP for the new type.
 487       //
 488       const PointerType *NewSrcTy = PointerType::get(PVTy);
 489       BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 490
 491       // Check to see if 'N' is an expression that can be converted to
 492       // the appropriate size... if so, allow it.
 493       //
 494       vector<Value*> Indices;
 495       const Type *ElTy = ConvertableToGEP(NewSrcTy, I->getOperand(1),
 496                                           Indices, &It);
 497       if (ElTy) {
 498         assert(ElTy == PVTy && "Internal error, setup wrong!");
 499         Res = new GetElementPtrInst(Constant::getNullConstant(NewSrcTy),
 500                                     Indices, Name);
 501         VMC.ExprMap[I] = Res;
 502         Res->setOperand(0, ConvertExpressionToType(I->getOperand(0),
 503                                                    NewSrcTy, VMC));
 504       }
 505     }
 506
 507     // Otherwise, it could be that we have something like this:
 508     //     getelementptr [[sbyte] *] * %reg115, uint %reg138    ; [sbyte]**
 509     // and want to convert it into something like this:
 510     //     getelemenptr [[int] *] * %reg115, uint %reg138      ; [int]**
 511     //
 512     if (Res == 0) {
 513       const PointerType *NewSrcTy = PointerType::get(PVTy);
 514       Res = new GetElementPtrInst(Constant::getNullConstant(NewSrcTy),
 515                                   GEP->copyIndices(), Name);
 516       VMC.ExprMap[I] = Res;
 517       Res->setOperand(0, ConvertExpressionToType(I->getOperand(0),
 518                                                  NewSrcTy, VMC));
 519     }
 520
 521
 522     assert(Res && "Didn't find match!");
 523     break;   // No match, maybe next time.
 524   }
 525
 526   default:
 527     assert(0 && "Expression convertable, but don't know how to convert?");
 528     return 0;
 529   }
 530
 531   assert(Res->getType() == Ty && "Didn't convert expr to correct type!");
 532
 533   BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 534   assert(It != BIL.end() && "Instruction not in own basic block??");
 535   BIL.insert(It, Res);
 536
 537   // Add the instruction to the expression map
 538   VMC.ExprMap[I] = Res;
 539
 540   // Expressions are only convertable if all of the users of the expression can
 541   // have this value converted.  This makes use of the map to avoid infinite
 542   // recursion.
 543   //
 544   unsigned NumUses = I->use_size();
 545   for (unsigned It = 0; It < NumUses; ) {
 546     unsigned OldSize = NumUses;
 547     ConvertOperandToType(*(I->use_begin()+It), I, Res, VMC);
 548     NumUses = I->use_size();
 549     if (NumUses == OldSize) ++It;
 550   }
 551
 552 #ifdef DEBUG_EXPR_CONVERT
 553   cerr << "ExpIn: " << (void*)I << " " << I
 554        << "ExpOut: " << (void*)Res << " " << Res;
 555 #endif
 556
 557   if (I->use_empty()) {
 558 #ifdef DEBUG_EXPR_CONVERT
 559     cerr << "EXPR DELETING: " << (void*)I << " " << I;
 560 #endif
 561     BIL.remove(I);
 562     VMC.OperandsMapped.erase(I);
 563     VMC.ExprMap.erase(I);
 564     delete I;
 565   }
 566
 567   return Res;
 568 }
 569
 570
 571
 572 // ValueConvertableToType - Return true if it is possible
 573 bool ValueConvertableToType(Value *V, const Type *Ty,
 574                              ValueTypeCache &ConvertedTypes) {
 575   ValueTypeCache::iterator I = ConvertedTypes.find(V);
 576   if (I != ConvertedTypes.end()) return I->second == Ty;
 577   ConvertedTypes[V] = Ty;
 578
 579   // It is safe to convert the specified value to the specified type IFF all of
 580   // the uses of the value can be converted to accept the new typed value.
 581   //
 582   for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I)
 583     if (!OperandConvertableToType(*I, V, Ty, ConvertedTypes))
 584       return false;
 585
 586   return true;
 587 }
 588
 589
 590
 591
 592
 593 // OperandConvertableToType - Return true if it is possible to convert operand
 594 // V of User (instruction) U to the specified type.  This is true iff it is
 595 // possible to change the specified instruction to accept this.  CTMap is a map
 596 // of converted types, so that circular definitions will see the future type of
 597 // the expression, not the static current type.
 598 //
 599 static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
 600                                      ValueTypeCache &CTMap) {
 601   //  if (V->getType() == Ty) return true;   // Operand already the right type?
 602
 603   // Expression type must be holdable in a register.
 604   if (!Ty->isFirstClassType())
 605     return false;
 606
 607   Instruction *I = dyn_cast<Instruction>(U);
 608   if (I == 0) return false;              // We can't convert!
 609
 610   switch (I->getOpcode()) {
 611   case Instruction::Cast:
 612     assert(I->getOperand(0) == V);
 613     // We can convert the expr if the cast destination type is losslessly
 614     // convertable to the requested type.
 615     // Also, do not change a cast that is a noop cast.  For all intents and
 616     // purposes it should be eliminated.
 617     if (!Ty->isLosslesslyConvertableTo(I->getOperand(0)->getType()) ||
 618         I->getType() == I->getOperand(0)->getType())
 619       return false;
 620
 621
 622 #if 1
 623     // We also do not allow conversion of a cast that casts from a ptr to array
 624     // of X to a *X.  For example: cast [4 x %List *] * %val to %List * *
 625     //
 626     if (PointerType *SPT = dyn_cast<PointerType>(I->getOperand(0)->getType()))
 627       if (PointerType *DPT = dyn_cast<PointerType>(I->getType()))
 628         if (ArrayType *AT = dyn_cast<ArrayType>(SPT->getElementType()))
 629           if (AT->getElementType() == DPT->getElementType())
 630             return false;
 631 #endif
 632     return true;
 633
 634   case Instruction::Add:
 635     if (isa<PointerType>(Ty)) {
 636       Value *IndexVal = I->getOperand(V == I->getOperand(0) ? 1 : 0);
 637       vector<Value*> Indices;
 638       if (const Type *ETy = ConvertableToGEP(Ty, IndexVal, Indices)) {
 639         const Type *RetTy = PointerType::get(ETy);
 640
 641         // Only successful if we can convert this type to the required type
 642         if (ValueConvertableToType(I, RetTy, CTMap)) {
 643           CTMap[I] = RetTy;
 644           return true;
 645         }
 646         // We have to return failure here because ValueConvertableToType could
 647         // have polluted our map
 648         return false;
 649       }
 650     }
 651     // FALLTHROUGH
 652   case Instruction::Sub: {
 653     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
 654     return ValueConvertableToType(I, Ty, CTMap) &&
 655            ExpressionConvertableToType(OtherOp, Ty, CTMap);
 656   }
 657   case Instruction::SetEQ:
 658   case Instruction::SetNE: {
 659     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
 660     return ExpressionConvertableToType(OtherOp, Ty, CTMap);
 661   }
 662   case Instruction::Shr:
 663     if (Ty->isSigned() != V->getType()->isSigned()) return false;
 664     // FALL THROUGH
 665   case Instruction::Shl:
 666     assert(I->getOperand(0) == V);
 667     return ValueConvertableToType(I, Ty, CTMap);
 668
 669   case Instruction::Free:
 670     assert(I->getOperand(0) == V);
 671     return isa<PointerType>(Ty);    // Free can free any pointer type!
 672
 673   case Instruction::Load:
 674     // Cannot convert the types of any subscripts...
 675     if (I->getOperand(0) != V) return false;
 676
 677     if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
 678       LoadInst *LI = cast<LoadInst>(I);
 679
 680       if (LI->hasIndices() && !AllIndicesZero(LI))
 681         return false;
 682
 683       const Type *LoadedTy = PT->getElementType();
 684
 685       // They could be loading the first element of a composite type...
 686       if (const CompositeType *CT = dyn_cast<CompositeType>(LoadedTy)) {
 687         unsigned Offset = 0;     // No offset, get first leaf.
 688         vector<Value*> Indices;  // Discarded...
 689         LoadedTy = getStructOffsetType(CT, Offset, Indices, false);
 690         assert(Offset == 0 && "Offset changed from zero???");
 691       }
 692
 693       if (!LoadedTy->isFirstClassType())
 694         return false;
 695
 696       if (TD.getTypeSize(LoadedTy) != TD.getTypeSize(LI->getType()))
 697         return false;
 698
 699       return ValueConvertableToType(LI, LoadedTy, CTMap);
 700     }
 701     return false;
 702
 703   case Instruction::Store: {
 704     StoreInst *SI = cast<StoreInst>(I);
 705     if (SI->hasIndices()) return false;
 706
 707     if (V == I->getOperand(0)) {
 708       // Can convert the store if we can convert the pointer operand to match
 709       // the new  value type...
 710       return ExpressionConvertableToType(I->getOperand(1), PointerType::get(Ty),
 711                                          CTMap);
 712     } else if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
 713       const Type *ElTy = PT->getElementType();
 714       assert(V == I->getOperand(1));
 715
 716       // Must move the same amount of data...
 717       if (TD.getTypeSize(ElTy) != TD.getTypeSize(I->getOperand(0)->getType()))
 718         return false;
 719
 720       // Can convert store if the incoming value is convertable...
 721       return ExpressionConvertableToType(I->getOperand(0), ElTy, CTMap);
 722     }
 723     return false;
 724   }
 725
 726   case Instruction::GetElementPtr:
 727     if (V != I->getOperand(0) || !isa<PointerType>(Ty)) return false;
 728
 729     // If we have a two operand form of getelementptr, this is really little
 730     // more than a simple addition.  As with addition, check to see if the
 731     // getelementptr instruction can be changed to index into the new type.
 732     //
 733     if (I->getNumOperands() == 2) {
 734       const Type *OldElTy = cast<PointerType>(I->getType())->getElementType();
 735       unsigned DataSize = TD.getTypeSize(OldElTy);
 736       Value *Index = I->getOperand(1);
 737       Instruction *TempScale = 0;
 738
 739       // If the old data element is not unit sized, we have to create a scale
 740       // instruction so that ConvertableToGEP will know the REAL amount we are
 741       // indexing by.  Note that this is never inserted into the instruction
 742       // stream, so we have to delete it when we're done.
 743       //
 744       if (DataSize != 1) {
 745         TempScale = BinaryOperator::create(Instruction::Mul, Index,
 746                                            ConstantUInt::get(Type::UIntTy,
 747                                                              DataSize));
 748         Index = TempScale;
 749       }
 750
 751       // Check to see if the second argument is an expression that can
 752       // be converted to the appropriate size... if so, allow it.
 753       //
 754       vector<Value*> Indices;
 755       const Type *ElTy = ConvertableToGEP(Ty, Index, Indices);
 756       delete TempScale;   // Free our temporary multiply if we made it
 757
 758       if (ElTy == 0) return false;  // Cannot make conversion...
 759       return ValueConvertableToType(I, PointerType::get(ElTy), CTMap);
 760     }
 761     return false;
 762
 763   case Instruction::PHINode: {
 764     PHINode *PN = cast<PHINode>(I);
 765     for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i)
 766       if (!ExpressionConvertableToType(PN->getIncomingValue(i), Ty, CTMap))
 767         return false;
 768     return ValueConvertableToType(PN, Ty, CTMap);
 769   }
 770
 771   case Instruction::Call: {
 772     User::op_iterator OI = find(I->op_begin(), I->op_end(), V);
 773     assert (OI != I->op_end() && "Not using value!");
 774     unsigned OpNum = OI - I->op_begin();
 775
 776     if (OpNum == 0)
 777       return false; // Can't convert method pointer type yet.  FIXME
 778
 779     const PointerType *MPtr = cast<PointerType>(I->getOperand(0)->getType());
 780     const MethodType *MTy = cast<MethodType>(MPtr->getElementType());
 781     if (!MTy->isVarArg()) return false;
 782
 783     if ((OpNum-1) < MTy->getParamTypes().size())
 784       return false;  // It's not in the varargs section...
 785
 786     // If we get this far, we know the value is in the varargs section of the
 787     // method!  We can convert if we don't reinterpret the value...
 788     //
 789     return Ty->isLosslesslyConvertableTo(V->getType());
 790   }
 791   }
 792   return false;
 793 }
 794
 795
 796 void ConvertValueToNewType(Value *V, Value *NewVal, ValueMapCache &VMC) {
 797   ValueHandle VH(VMC, V);
 798
 799   unsigned NumUses = V->use_size();
 800   for (unsigned It = 0; It < NumUses; ) {
 801     unsigned OldSize = NumUses;
 802     ConvertOperandToType(*(V->use_begin()+It), V, NewVal, VMC);
 803     NumUses = V->use_size();
 804     if (NumUses == OldSize) ++It;
 805   }
 806 }
 807
 808
 809
 810 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
 811                                  ValueMapCache &VMC) {
 812   if (isa<ValueHandle>(U)) return;  // Valuehandles don't let go of operands...
 813
 814   if (VMC.OperandsMapped.count(U)) return;
 815   VMC.OperandsMapped.insert(U);
 816
 817   ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(U);
 818   if (VMCI != VMC.ExprMap.end())
 819     return;
 820
 821
 822   Instruction *I = cast<Instruction>(U);  // Only Instructions convertable
 823
 824   BasicBlock *BB = I->getParent();
 825   BasicBlock::InstListType &BIL = BB->getInstList();
 826   string Name = I->getName();  if (!Name.empty()) I->setName("");
 827   Instruction *Res;     // Result of conversion
 828
 829   //cerr << endl << endl << "Type:\t" << Ty << "\nInst: " << I << "BB Before: " << BB << endl;
 830
 831   // Prevent I from being removed...
 832   ValueHandle IHandle(VMC, I);
 833
 834   const Type *NewTy = NewVal->getType();
 835   Constant *Dummy = (NewTy != Type::VoidTy) ?
 836                   Constant::getNullConstant(NewTy) : 0;
 837
 838   switch (I->getOpcode()) {
 839   case Instruction::Cast:
 840     assert(I->getOperand(0) == OldVal);
 841     Res = new CastInst(NewVal, I->getType(), Name);
 842     break;
 843
 844   case Instruction::Add:
 845     if (isa<PointerType>(NewTy)) {
 846       Value *IndexVal = I->getOperand(OldVal == I->getOperand(0) ? 1 : 0);
 847       vector<Value*> Indices;
 848       BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 849
 850       if (const Type *ETy = ConvertableToGEP(NewTy, IndexVal, Indices, &It)) {
 851         // If successful, convert the add to a GEP
 852         const Type *RetTy = PointerType::get(ETy);
 853         // First operand is actually the given pointer...
 854         Res = new GetElementPtrInst(NewVal, Indices, Name);
 855         assert(cast<PointerType>(Res->getType())->getElementType() == ETy &&
 856                "ConvertableToGEP broken!");
 857         break;
 858       }
 859     }
 860     // FALLTHROUGH
 861
 862   case Instruction::Sub:
 863   case Instruction::SetEQ:
 864   case Instruction::SetNE: {
 865     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
 866                                  Dummy, Dummy, Name);
 867     VMC.ExprMap[I] = Res;   // Add node to expression eagerly
 868
 869     unsigned OtherIdx = (OldVal == I->getOperand(0)) ? 1 : 0;
 870     Value *OtherOp    = I->getOperand(OtherIdx);
 871     Value *NewOther   = ConvertExpressionToType(OtherOp, NewTy, VMC);
 872
 873     Res->setOperand(OtherIdx, NewOther);
 874     Res->setOperand(!OtherIdx, NewVal);
 875     break;
 876   }
 877   case Instruction::Shl:
 878   case Instruction::Shr:
 879     assert(I->getOperand(0) == OldVal);
 880     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), NewVal,
 881                         I->getOperand(1), Name);
 882     break;
 883
 884   case Instruction::Free:            // Free can free any pointer type!
 885     assert(I->getOperand(0) == OldVal);
 886     Res = new FreeInst(NewVal);
 887     break;
 888
 889
 890   case Instruction::Load: {
 891     assert(I->getOperand(0) == OldVal && isa<PointerType>(NewVal->getType()));
 892     const Type *LoadedTy =
 893       cast<PointerType>(NewVal->getType())->getElementType();
 894
 895     vector<Value*> Indices;
 896     Indices.push_back(ConstantUInt::get(Type::UIntTy, 0));
 897
 898     if (const CompositeType *CT = dyn_cast<CompositeType>(LoadedTy)) {
 899       unsigned Offset = 0;   // No offset, get first leaf.
 900       LoadedTy = getStructOffsetType(CT, Offset, Indices, false);
 901     }
 902     assert(LoadedTy->isFirstClassType());
 903
 904     Res = new LoadInst(NewVal, Indices, Name);
 905     assert(Res->getType()->isFirstClassType() && "Load of structure or array!");
 906     break;
 907   }
 908
 909   case Instruction::Store: {
 910     if (I->getOperand(0) == OldVal) {  // Replace the source value
 911       const PointerType *NewPT = PointerType::get(NewTy);
 912       Res = new StoreInst(NewVal, Constant::getNullConstant(NewPT));
 913       VMC.ExprMap[I] = Res;
 914       Res->setOperand(1, ConvertExpressionToType(I->getOperand(1), NewPT, VMC));
 915     } else {                           // Replace the source pointer
 916       const Type *ValTy = cast<PointerType>(NewTy)->getElementType();
 917       vector<Value*> Indices;
 918 #if 0
 919       Indices.push_back(ConstantUInt::get(Type::UIntTy, 0));
 920       while (ArrayType *AT = dyn_cast<ArrayType>(ValTy)) {
 921         Indices.push_back(ConstantUInt::get(Type::UIntTy, 0));
 922         ValTy = AT->getElementType();
 923       }
 924 #endif
 925       Res = new StoreInst(Constant::getNullConstant(ValTy), NewVal, Indices);
 926       VMC.ExprMap[I] = Res;
 927       Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), ValTy, VMC));
 928     }
 929     break;
 930   }
 931
 932
 933   case Instruction::GetElementPtr: {
 934     // Convert a one index getelementptr into just about anything that is
 935     // desired.
 936     //
 937     BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 938     const Type *OldElTy = cast<PointerType>(I->getType())->getElementType();
 939     unsigned DataSize = TD.getTypeSize(OldElTy);
 940     Value *Index = I->getOperand(1);
 941
 942     if (DataSize != 1) {
 943       // Insert a multiply of the old element type is not a unit size...
 944       Index = BinaryOperator::create(Instruction::Mul, Index,
 945                                      ConstantUInt::get(Type::UIntTy, DataSize));
 946       It = BIL.insert(It, cast<Instruction>(Index))+1;
 947     }
 948
 949     // Perform the conversion now...
 950     //
 951     vector<Value*> Indices;
 952     const Type *ElTy = ConvertableToGEP(NewVal->getType(), Index, Indices, &It);
 953     assert(ElTy != 0 && "GEP Conversion Failure!");
 954     Res = new GetElementPtrInst(NewVal, Indices, Name);
 955     assert(Res->getType() == PointerType::get(ElTy) &&
 956            "ConvertableToGet failed!");
 957   }
 958 #if 0
 959     if (I->getType() == PointerType::get(Type::SByteTy)) {
 960       // Convert a getelementptr sbyte * %reg111, uint 16 freely back to
 961       // anything that is a pointer type...
 962       //
 963       BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 964
 965       // Check to see if the second argument is an expression that can
 966       // be converted to the appropriate size... if so, allow it.
 967       //
 968       vector<Value*> Indices;
 969       const Type *ElTy = ConvertableToGEP(NewVal->getType(), I->getOperand(1),
 970                                           Indices, &It);
 971       assert(ElTy != 0 && "GEP Conversion Failure!");
 972
 973       Res = new GetElementPtrInst(NewVal, Indices, Name);
 974     } else {
 975       // Convert a getelementptr ulong * %reg123, uint %N
 976       // to        getelementptr  long * %reg123, uint %N
 977       // ... where the type must simply stay the same size...
 978       //
 979       Res = new GetElementPtrInst(NewVal,
 980                                   cast<GetElementPtrInst>(I)->copyIndices(),
 981                                   Name);
 982     }
 983 #endif
 984     break;
 985
 986   case Instruction::PHINode: {
 987     PHINode *OldPN = cast<PHINode>(I);
 988     PHINode *NewPN = new PHINode(NewTy, Name);
 989     VMC.ExprMap[I] = NewPN;
 990
 991     while (OldPN->getNumOperands()) {
 992       BasicBlock *BB = OldPN->getIncomingBlock(0);
 993       Value *OldVal = OldPN->getIncomingValue(0);
 994       OldPN->removeIncomingValue(BB);
 995       Value *V = ConvertExpressionToType(OldVal, NewTy, VMC);
 996       NewPN->addIncoming(V, BB);
 997     }
 998     Res = NewPN;
 999     break;
1000   }
1001
1002   case Instruction::Call: {
1003     Value *Meth = I->getOperand(0);
1004     vector<Value*> Params(I->op_begin()+1, I->op_end());
1005
1006     vector<Value*>::iterator OI = find(Params.begin(), Params.end(), OldVal);
1007     assert (OI != Params.end() && "Not using value!");
1008
1009     *OI = NewVal;
1010     Res = new CallInst(Meth, Params, Name);
1011     break;
1012   }
1013   default:
1014     assert(0 && "Expression convertable, but don't know how to convert?");
1015     return;
1016   }
1017
1018   // If the instruction was newly created, insert it into the instruction
1019   // stream.
1020   //
1021   BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
1022   assert(It != BIL.end() && "Instruction not in own basic block??");
1023   BIL.insert(It, Res);   // Keep It pointing to old instruction
1024
1025 #ifdef DEBUG_EXPR_CONVERT
1026   cerr << "COT CREATED: "  << (void*)Res << " " << Res;
1027   cerr << "In: " << (void*)I << " " << I << "Out: " << (void*)Res << " " << Res;
1028 #endif
1029
1030   // Add the instruction to the expression map
1031   VMC.ExprMap[I] = Res;
1032
1033   if (I->getType() != Res->getType())
1034     ConvertValueToNewType(I, Res, VMC);
1035   else {
1036     for (unsigned It = 0; It < I->use_size(); ) {
1037       User *Use = *(I->use_begin()+It);
1038       if (isa<ValueHandle>(Use))            // Don't remove ValueHandles!
1039         ++It;
1040       else
1041         Use->replaceUsesOfWith(I, Res);
1042     }
1043
1044     if (I->use_empty()) {
1045       // Now we just need to remove the old instruction so we don't get infinite
1046       // loops.  Note that we cannot use DCE because DCE won't remove a store
1047       // instruction, for example.
1048       //
1049 #ifdef DEBUG_EXPR_CONVERT
1050       cerr << "DELETING: " << (void*)I << " " << I;
1051 #endif
1052       BIL.remove(I);
1053       VMC.OperandsMapped.erase(I);
1054       VMC.ExprMap.erase(I);
1055       delete I;
1056     } else {
1057       for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
1058            UI != UE; ++UI)
1059         assert(isa<ValueHandle>((Value*)*UI) &&"Uses of Instruction remain!!!");
1060     }
1061   }
1062 }
1063
1064
1065 ValueHandle::ValueHandle(ValueMapCache &VMC, Value *V)
1066   : Instruction(Type::VoidTy, UserOp1, ""), Cache(VMC) {
1067 #ifdef DEBUG_EXPR_CONVERT
1068   //cerr << "VH AQUIRING: " << (void*)V << " " << V;
1069 #endif
1070   Operands.push_back(Use(V, this));
1071 }
1072
1073 static void RecursiveDelete(ValueMapCache &Cache, Instruction *I) {
1074   if (!I || !I->use_empty()) return;
1075
1076   assert(I->getParent() && "Inst not in basic block!");
1077
1078 #ifdef DEBUG_EXPR_CONVERT
1079   //cerr << "VH DELETING: " << (void*)I << " " << I;
1080 #endif
1081
1082   for (User::op_iterator OI = I->op_begin(), OE = I->op_end();
1083        OI != OE; ++OI) {
1084     Instruction *U = dyn_cast<Instruction>(*OI);
1085     if (U) {
1086       *OI = 0;
1087       RecursiveDelete(Cache, dyn_cast<Instruction>(U));
1088     }
1089   }
1090
1091   I->getParent()->getInstList().remove(I);
1092
1093   Cache.OperandsMapped.erase(I);
1094   Cache.ExprMap.erase(I);
1095   delete I;
1096 }
1097
1098 ValueHandle::~ValueHandle() {
1099   if (Operands[0]->use_size() == 1) {
1100     Value *V = Operands[0];
1101     Operands[0] = 0;   // Drop use!
1102
1103     // Now we just need to remove the old instruction so we don't get infinite
1104     // loops.  Note that we cannot use DCE because DCE won't remove a store
1105     // instruction, for example.
1106     //
1107     RecursiveDelete(Cache, dyn_cast<Instruction>(V));
1108   } else {
1109 #ifdef DEBUG_EXPR_CONVERT
1110     //cerr << "VH RELEASING: " << (void*)Operands[0].get() << " " << Operands[0]->use_size() << " " << Operands[0];
1111 #endif
1112   }
1113 }