lib/Transforms/ExprTypeConvert.cpp

   1 //===- ExprTypeConvert.cpp - Code to change an LLVM Expr Type ---------------=//
   2 //
   3 // This file implements the part of level raising that checks to see if it is
   4 // possible to coerce an entire expression tree into a different type.  If
   5 // convertable, other routines from this file will do the conversion.
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "TransformInternals.h"
  10 #include "llvm/Method.h"
  11 #include "llvm/Support/STLExtras.h"
  12 #include "llvm/iOther.h"
  13 #include "llvm/iMemory.h"
  14 #include "llvm/ConstPoolVals.h"
  15 #include "llvm/Optimizations/ConstantHandling.h"
  16 #include "llvm/Optimizations/DCE.h"
  17 #include <map>
  18 #include <algorithm>
  19
  20 #include "llvm/Assembly/Writer.h"
  21
  22 // ExpressionConvertableToType - Return true if it is possible
  23 static bool ExpressionConvertableToType(Value *V, const Type *Ty,
  24                                         ValueTypeCache &CTMap) {
  25   ValueTypeCache::iterator CTMI = CTMap.find(V);
  26   if (CTMI != CTMap.end()) return CTMI->second == Ty;
  27   CTMap[V] = Ty;
  28
  29   Instruction *I = dyn_cast<Instruction>(V);
  30   if (I == 0) {
  31     // It's not an instruction, check to see if it's a constant... all constants
  32     // can be converted to an equivalent value (except pointers, they can't be
  33     // const prop'd in general).
  34     //
  35     if (isa<ConstPoolVal>(V) &&
  36         !isa<PointerType>(V->getType()) && !isa<PointerType>(Ty)) return true;
  37
  38     return false;              // Otherwise, we can't convert!
  39   }
  40   if (I->getType() == Ty) return false;  // Expression already correct type!
  41
  42   switch (I->getOpcode()) {
  43   case Instruction::Cast:
  44     // We can convert the expr if the cast destination type is losslessly
  45     // convertable to the requested type.
  46     return losslessCastableTypes(Ty, I->getType());
  47
  48   case Instruction::Add:
  49   case Instruction::Sub:
  50     return ExpressionConvertableToType(I->getOperand(0), Ty, CTMap) &&
  51            ExpressionConvertableToType(I->getOperand(1), Ty, CTMap);
  52   case Instruction::Shr:
  53     if (Ty->isSigned() != V->getType()->isSigned()) return false;
  54     // FALL THROUGH
  55   case Instruction::Shl:
  56     return ExpressionConvertableToType(I->getOperand(0), Ty, CTMap);
  57
  58   case Instruction::Load: {
  59     LoadInst *LI = cast<LoadInst>(I);
  60     if (LI->hasIndices()) return false;
  61     return ExpressionConvertableToType(LI->getPtrOperand(),
  62                                        PointerType::get(Ty), CTMap);
  63   }
  64   case Instruction::GetElementPtr: {
  65     // GetElementPtr's are directly convertable to a pointer type if they have
  66     // a number of zeros at the end.  Because removing these values does not
  67     // change the logical offset of the GEP, it is okay and fair to remove them.
  68     // This can change this:
  69     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
  70     //   %t2 = cast %List * * %t1 to %List *
  71     // into
  72     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
  73     //
  74     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
  75     const PointerType *PTy = dyn_cast<PointerType>(Ty);
  76     if (!PTy) return false;
  77
  78     // Check to see if there are zero elements that we can remove from the
  79     // index array.  If there are, check to see if removing them causes us to
  80     // get to the right type...
  81     //
  82     vector<ConstPoolVal*> Indices = GEP->getIndices();
  83     const Type *BaseType = GEP->getPtrOperand()->getType();
  84
  85     while (Indices.size() &&
  86            cast<ConstPoolUInt>(Indices.back())->getValue() == 0) {
  87       Indices.pop_back();
  88       const Type *ElTy = GetElementPtrInst::getIndexedType(BaseType, Indices,
  89                                                            true);
  90       if (ElTy == PTy->getValueType())
  91         return true;  // Found a match!!
  92     }
  93     break;   // No match, maybe next time.
  94   }
  95   }
  96   return false;
  97 }
  98
  99
 100
 101
 102 static Value *ConvertExpressionToType(Value *V, const Type *Ty,
 103                                       ValueMapCache &VMC) {
 104   Instruction *I = dyn_cast<Instruction>(V);
 105   if (I == 0)
 106     if (ConstPoolVal *CPV = cast<ConstPoolVal>(V)) {
 107       // Constants are converted by constant folding the cast that is required.
 108       // We assume here that all casts are implemented for constant prop.
 109       Value *Result = opt::ConstantFoldCastInstruction(CPV, Ty);
 110       if (!Result) cerr << "Couldn't fold " << CPV << " to " << Ty << endl;
 111       assert(Result && "ConstantFoldCastInstruction Failed!!!");
 112       return Result;
 113     }
 114
 115
 116   BasicBlock *BB = I->getParent();
 117   BasicBlock::InstListType &BIL = BB->getInstList();
 118   string Name = I->getName();  if (!Name.empty()) I->setName("");
 119   Instruction *Res;     // Result of conversion
 120
 121   //cerr << endl << endl << "Type:\t" << Ty << "\nInst: " << I << "BB Before: " << BB << endl;
 122
 123   switch (I->getOpcode()) {
 124   case Instruction::Cast:
 125     Res = new CastInst(I->getOperand(0), Ty, Name);
 126     break;
 127
 128   case Instruction::Add:
 129   case Instruction::Sub:
 130     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
 131                              ConvertExpressionToType(I->getOperand(0), Ty, VMC),
 132                              ConvertExpressionToType(I->getOperand(1), Ty, VMC),
 133                                  Name);
 134     break;
 135
 136   case Instruction::Shl:
 137   case Instruction::Shr:
 138     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(),
 139                         ConvertExpressionToType(I->getOperand(0), Ty, VMC),
 140                         I->getOperand(1), Name);
 141     break;
 142
 143   case Instruction::Load: {
 144     LoadInst *LI = cast<LoadInst>(I);
 145     assert(!LI->hasIndices());
 146     Res = new LoadInst(ConvertExpressionToType(LI->getPtrOperand(),
 147                                                PointerType::get(Ty), VMC),
 148                        Name);
 149     break;
 150   }
 151
 152   case Instruction::GetElementPtr: {
 153     // GetElementPtr's are directly convertable to a pointer type if they have
 154     // a number of zeros at the end.  Because removing these values does not
 155     // change the logical offset of the GEP, it is okay and fair to remove them.
 156     // This can change this:
 157     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 158     //   %t2 = cast %List * * %t1 to %List *
 159     // into
 160     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 161     //
 162     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 163
 164     // Check to see if there are zero elements that we can remove from the
 165     // index array.  If there are, check to see if removing them causes us to
 166     // get to the right type...
 167     //
 168     vector<ConstPoolVal*> Indices = GEP->getIndices();
 169     const Type *BaseType = GEP->getPtrOperand()->getType();
 170     const Type *PVTy = cast<PointerType>(Ty)->getValueType();
 171     Res = 0;
 172     while (Indices.size() &&
 173            cast<ConstPoolUInt>(Indices.back())->getValue() == 0) {
 174       Indices.pop_back();
 175       if (GetElementPtrInst::getIndexedType(BaseType, Indices, true) == PVTy) {
 176         if (Indices.size() == 0) {
 177           Res = new CastInst(GEP->getPtrOperand(), BaseType); // NOOP
 178         } else {
 179           Res = new GetElementPtrInst(GEP->getPtrOperand(), Indices, Name);
 180         }
 181         break;
 182       }
 183     }
 184     assert(Res && "Didn't find match!");
 185     break;   // No match, maybe next time.
 186   }
 187
 188   default:
 189     assert(0 && "Expression convertable, but don't know how to convert?");
 190     return 0;
 191   }
 192
 193   BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 194   assert(It != BIL.end() && "Instruction not in own basic block??");
 195   BIL.insert(It, Res);
 196
 197   //cerr << "RInst: " << Res << "BB After: " << BB << endl << endl;
 198
 199   return Res;
 200 }
 201
 202
 203
 204
 205
 206
 207
 208 static inline const Type *getTy(const Value *V, ValueTypeCache &CT) {
 209   ValueTypeCache::iterator I = CT.find(V);
 210   if (I == CT.end()) return V->getType();
 211   return I->second;
 212 }
 213
 214
 215 static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
 216                                      ValueTypeCache &ConvertedTypes);
 217
 218 // RetValConvertableToType - Return true if it is possible
 219 bool RetValConvertableToType(Value *V, const Type *Ty,
 220                              ValueTypeCache &ConvertedTypes) {
 221   ValueTypeCache::iterator I = ConvertedTypes.find(V);
 222   if (I != ConvertedTypes.end()) return I->second == Ty;
 223   ConvertedTypes[V] = Ty;
 224
 225   // It is safe to convert the specified value to the specified type IFF all of
 226   // the uses of the value can be converted to accept the new typed value.
 227   //
 228   for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I)
 229     if (!OperandConvertableToType(*I, V, Ty, ConvertedTypes))
 230       return false;
 231
 232   return true;
 233 }
 234
 235
 236 // OperandConvertableToType - Return true if it is possible to convert operand
 237 // V of User (instruction) U to the specified type.  This is true iff it is
 238 // possible to change the specified instruction to accept this.  CTMap is a map
 239 // of converted types, so that circular definitions will see the future type of
 240 // the expression, not the static current type.
 241 //
 242 static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
 243                                      ValueTypeCache &CTMap) {
 244   assert(V->getType() != Ty &&
 245          "OperandConvertableToType: Operand is already right type!");
 246   Instruction *I = dyn_cast<Instruction>(U);
 247   if (I == 0) return false;              // We can't convert!
 248
 249   switch (I->getOpcode()) {
 250   case Instruction::Cast:
 251     assert(I->getOperand(0) == V);
 252     // We can convert the expr if the cast destination type is losslessly
 253     // convertable to the requested type.
 254     return losslessCastableTypes(Ty, I->getOperand(0)->getType());
 255
 256   case Instruction::Add:
 257   case Instruction::Sub: {
 258     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
 259     return RetValConvertableToType(I, Ty, CTMap) &&
 260            ExpressionConvertableToType(OtherOp, Ty, CTMap);
 261   }
 262   case Instruction::SetEQ:
 263   case Instruction::SetNE: {
 264     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
 265     return ExpressionConvertableToType(OtherOp, Ty, CTMap);
 266   }
 267   case Instruction::Shr:
 268     if (Ty->isSigned() != V->getType()->isSigned()) return false;
 269     // FALL THROUGH
 270   case Instruction::Shl:
 271     assert(I->getOperand(0) == V);
 272     return RetValConvertableToType(I, Ty, CTMap);
 273
 274   case Instruction::Load:
 275     assert(I->getOperand(0) == V);
 276     if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
 277       LoadInst *LI = cast<LoadInst>(I);
 278       if (LI->hasIndices() ||
 279           TD.getTypeSize(PT->getValueType()) != TD.getTypeSize(LI->getType()))
 280         return false;
 281
 282       return RetValConvertableToType(LI, PT->getValueType(), CTMap);
 283     }
 284     return false;
 285
 286   case Instruction::Store: {
 287     StoreInst *SI = cast<StoreInst>(I);
 288     if (SI->hasIndices()) return false;
 289
 290     if (V == I->getOperand(0)) {
 291       // Can convert the store if we can convert the pointer operand to match
 292       // the new  value type...
 293       return ExpressionConvertableToType(I->getOperand(1), PointerType::get(Ty),
 294                                          CTMap);
 295     } else if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
 296       if (isa<ArrayType>(PT->getValueType()))
 297         return false;  // Avoid getDataSize on unsized array type!
 298       assert(V == I->getOperand(1));
 299
 300       // Must move the same amount of data...
 301       if (TD.getTypeSize(PT->getValueType()) !=
 302           TD.getTypeSize(I->getOperand(0)->getType())) return false;
 303
 304       // Can convert store if the incoming value is convertable...
 305       return ExpressionConvertableToType(I->getOperand(0), PT->getValueType(),
 306                                          CTMap);
 307     }
 308     return false;
 309   }
 310
 311
 312 #if 0
 313   case Instruction::GetElementPtr: {
 314     // GetElementPtr's are directly convertable to a pointer type if they have
 315     // a number of zeros at the end.  Because removing these values does not
 316     // change the logical offset of the GEP, it is okay and fair to remove them.
 317     // This can change this:
 318     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 319     //   %t2 = cast %List * * %t1 to %List *
 320     // into
 321     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 322     //
 323     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 324     const PointerType *PTy = dyn_cast<PointerType>(Ty);
 325     if (!PTy) return false;
 326
 327     // Check to see if there are zero elements that we can remove from the
 328     // index array.  If there are, check to see if removing them causes us to
 329     // get to the right type...
 330     //
 331     vector<ConstPoolVal*> Indices = GEP->getIndices();
 332     const Type *BaseType = GEP->getPtrOperand()->getType();
 333
 334     while (Indices.size() &&
 335            cast<ConstPoolUInt>(Indices.back())->getValue() == 0) {
 336       Indices.pop_back();
 337       const Type *ElTy = GetElementPtrInst::getIndexedType(BaseType, Indices,
 338                                                            true);
 339       if (ElTy == PTy->getValueType())
 340         return true;  // Found a match!!
 341     }
 342     break;   // No match, maybe next time.
 343   }
 344 #endif
 345   }
 346   return false;
 347 }
 348
 349
 350
 351
 352
 353
 354 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
 355                                  ValueMapCache &VMC);
 356
 357 void ConvertUsersType(Value *V, Value *NewVal, ValueMapCache &VMC) {
 358
 359   // It is safe to convert the specified value to the specified type IFF all of
 360   // the uses of the value can be converted to accept the new typed value.
 361   //
 362   while (!V->use_empty()) {
 363     unsigned OldSize = V->use_size();
 364     ConvertOperandToType(V->use_back(), V, NewVal, VMC);
 365     assert(V->use_size() != OldSize && "Use didn't detatch from value!");
 366   }
 367 }
 368
 369
 370
 371 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
 372                                  ValueMapCache &VMC) {
 373   Instruction *I = cast<Instruction>(U);  // Only Instructions convertable
 374
 375   BasicBlock *BB = I->getParent();
 376   BasicBlock::InstListType &BIL = BB->getInstList();
 377   string Name = I->getName();  if (!Name.empty()) I->setName("");
 378   Instruction *Res;     // Result of conversion
 379
 380   //cerr << endl << endl << "Type:\t" << Ty << "\nInst: " << I << "BB Before: " << BB << endl;
 381
 382   switch (I->getOpcode()) {
 383   case Instruction::Cast:
 384     assert(I->getOperand(0) == OldVal);
 385     Res = new CastInst(NewVal, I->getType(), Name);
 386     break;
 387
 388   case Instruction::Add:
 389   case Instruction::Sub:
 390   case Instruction::SetEQ:
 391   case Instruction::SetNE: {
 392     unsigned OtherIdx = (OldVal == I->getOperand(0)) ? 1 : 0;
 393     Value *OtherOp    = I->getOperand(OtherIdx);
 394     Value *NewOther   = ConvertExpressionToType(OtherOp, NewVal->getType(),VMC);
 395
 396     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
 397                                  OtherIdx == 0 ? NewOther : NewVal,
 398                                  OtherIdx == 1 ? NewOther : NewVal,
 399                                  Name);
 400     break;
 401   }
 402   case Instruction::Shl:
 403   case Instruction::Shr:
 404     assert(I->getOperand(0) == OldVal);
 405     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), NewVal,
 406                         I->getOperand(1), Name);
 407     break;
 408
 409   case Instruction::Load:
 410     assert(I->getOperand(0) == OldVal);
 411     Res = new LoadInst(NewVal, Name);
 412     break;
 413
 414   case Instruction::Store: {
 415     if (I->getOperand(0) == OldVal) {  // Replace the source value
 416       Value *NewPtr =
 417         ConvertExpressionToType(I->getOperand(1),
 418                                 PointerType::get(NewVal->getType()), VMC);
 419       Res = new StoreInst(NewVal, NewPtr);
 420     } else {                           // Replace the source pointer
 421       const Type *ValType =cast<PointerType>(NewVal->getType())->getValueType();
 422       Value *NewV = ConvertExpressionToType(I->getOperand(0), ValType, VMC);
 423       Res = new StoreInst(NewV, NewVal);
 424     }
 425     break;
 426   }
 427
 428 #if 0
 429   case Instruction::GetElementPtr: {
 430     // GetElementPtr's are directly convertable to a pointer type if they have
 431     // a number of zeros at the end.  Because removing these values does not
 432     // change the logical offset of the GEP, it is okay and fair to remove them.
 433     // This can change this:
 434     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 435     //   %t2 = cast %List * * %t1 to %List *
 436     // into
 437     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 438     //
 439     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 440
 441     // Check to see if there are zero elements that we can remove from the
 442     // index array.  If there are, check to see if removing them causes us to
 443     // get to the right type...
 444     //
 445     vector<ConstPoolVal*> Indices = GEP->getIndices();
 446     const Type *BaseType = GEP->getPtrOperand()->getType();
 447     const Type *PVTy = cast<PointerType>(Ty)->getValueType();
 448     Res = 0;
 449     while (Indices.size() &&
 450            cast<ConstPoolUInt>(Indices.back())->getValue() == 0) {
 451       Indices.pop_back();
 452       if (GetElementPtrInst::getIndexedType(BaseType, Indices, true) == PVTy) {
 453         if (Indices.size() == 0) {
 454           Res = new CastInst(GEP->getPtrOperand(), BaseType); // NOOP
 455         } else {
 456           Res = new GetElementPtrInst(GEP->getPtrOperand(), Indices, Name);
 457         }
 458         break;
 459       }
 460     }
 461     assert(Res && "Didn't find match!");
 462     break;   // No match, maybe next time.
 463   }
 464 #endif
 465
 466   default:
 467     assert(0 && "Expression convertable, but don't know how to convert?");
 468     return;
 469   }
 470
 471   BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 472   assert(It != BIL.end() && "Instruction not in own basic block??");
 473   BIL.insert(It, Res);   // Keep It pointing to old instruction
 474
 475 #if DEBUG_PEEPHOLE_INSTS
 476   cerr << "In: " << I << "Out: " << Res;
 477 #endif
 478
 479   //cerr << "RInst: " << Res << "BB After: " << BB << endl << endl;
 480
 481   if (I->getType() != Res->getType())
 482     ConvertUsersType(I, Res, VMC);
 483   else
 484     I->replaceAllUsesWith(Res);
 485
 486   // Now we just need to remove the old instruction so we don't get infinite
 487   // loops.  Note that we cannot use DCE because DCE won't remove a store
 488   // instruction, for example.
 489   assert(I->use_size() == 0 && "Uses of Instruction remain!!!");
 490
 491   It = find(BIL.begin(), BIL.end(), I);
 492   assert(It != BIL.end() && "Instruction no longer in basic block??");
 493   delete BIL.remove(It);
 494 }