lib/Transforms/LevelRaise.cpp

   1 //===- LevelRaise.cpp - Code to change LLVM to higher level -----------------=//
   2 //
   3 // This file implements the 'raising' part of the LevelChange API.  This is
   4 // useful because, in general, it makes the LLVM code terser and easier to
   5 // analyze.  Note that it is good to run DCE after doing this transformation.
   6 //
   7 //  Eliminate silly things in the source that do not effect the level, but do
   8 //  clean up the code:
   9 //    * Casts of casts
  10 //    - getelementptr/load & getelementptr/store are folded into a direct
  11 //      load or store
  12 //    - Convert this code (for both alloca and malloc):
  13 //          %reg110 = shl uint %n, ubyte 2          ;;<uint>
  14 //          %reg108 = alloca ubyte, uint %reg110            ;;<ubyte*>
  15 //          %cast76 = cast ubyte* %reg108 to uint*          ;;<uint*>
  16 //      To: %cast76 = alloca uint, uint %n
  17 //   Convert explicit addressing to use getelementptr instruction where possible
  18 //      - ...
  19 //
  20 //   Convert explicit addressing on pointers to use getelementptr instruction.
  21 //    - If a pointer is used by arithmetic operation, insert an array casted
  22 //      version into the source program, only for the following pointer types:
  23 //        * Method argument pointers
  24 //        - Pointers returned by alloca or malloc
  25 //        - Pointers returned by function calls
  26 //    - If a pointer is indexed with a value scaled by a constant size equal
  27 //      to the element size of the array, the expression is replaced with a
  28 //      getelementptr instruction.
  29 //
  30 //===----------------------------------------------------------------------===//
  31
  32 #include "llvm/Transforms/LevelChange.h"
  33 #include "llvm/Method.h"
  34 #include "llvm/Support/STLExtras.h"
  35 #include "llvm/iOther.h"
  36 #include "llvm/iMemory.h"
  37 #include "llvm/ConstPoolVals.h"
  38 #include "llvm/Target/TargetData.h"
  39 #include "llvm/Optimizations/ConstantHandling.h"
  40 #include "llvm/Optimizations/DCE.h"
  41 #include <map>
  42 #include <algorithm>
  43
  44 #include "llvm/Assembly/Writer.h"
  45
  46 //#define DEBUG_PEEPHOLE_INSTS 1
  47
  48 #ifdef DEBUG_PEEPHOLE_INSTS
  49 #define PRINT_PEEPHOLE(ID, NUM, I)            \
  50   cerr << "Inst P/H " << ID << "[" << NUM << "] " << I;
  51 #else
  52 #define PRINT_PEEPHOLE(ID, NUM, I)
  53 #endif
  54
  55 #define PRINT_PEEPHOLE1(ID, I1) do { PRINT_PEEPHOLE(ID, 0, I1); } while (0)
  56 #define PRINT_PEEPHOLE2(ID, I1, I2) \
  57   do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); } while (0)
  58 #define PRINT_PEEPHOLE3(ID, I1, I2, I3) \
  59   do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); \
  60        PRINT_PEEPHOLE(ID, 2, I3); } while (0)
  61
  62
  63 // TargetData Hack: Eventually we will have annotations given to us by the
  64 // backend so that we know stuff about type size and alignments.  For now
  65 // though, just use this, because it happens to match the model that GCC uses.
  66 //
  67 const TargetData TD("LevelRaise: Should be GCC though!");
  68
  69
  70 // losslessCastableTypes - Return true if the types are bitwise equivalent.
  71 // This predicate returns true if it is possible to cast from one type to
  72 // another without gaining or losing precision, or altering the bits in any way.
  73 //
  74 static bool losslessCastableTypes(const Type *T1, const Type *T2) {
  75   if (!T1->isPrimitiveType() && !isa<PointerType>(T1)) return false;
  76   if (!T2->isPrimitiveType() && !isa<PointerType>(T2)) return false;
  77
  78   if (T1->getPrimitiveID() == T2->getPrimitiveID())
  79     return true;  // Handles identity cast, and cast of differing pointer types
  80
  81   // Now we know that they are two differing primitive or pointer types
  82   switch (T1->getPrimitiveID()) {
  83   case Type::UByteTyID:   return T2 == Type::SByteTy;
  84   case Type::SByteTyID:   return T2 == Type::UByteTy;
  85   case Type::UShortTyID:  return T2 == Type::ShortTy;
  86   case Type::ShortTyID:   return T2 == Type::UShortTy;
  87   case Type::UIntTyID:    return T2 == Type::IntTy;
  88   case Type::IntTyID:     return T2 == Type::UIntTy;
  89   case Type::ULongTyID:
  90   case Type::LongTyID:
  91   case Type::PointerTyID:
  92     return T2 == Type::ULongTy || T2 == Type::LongTy ||
  93            T2->getPrimitiveID() == Type::PointerTyID;
  94   default:
  95     return false;  // Other types have no identity values
  96   }
  97 }
  98
  99
 100 // isReinterpretingCast - Return true if the cast instruction specified will
 101 // cause the operand to be "reinterpreted".  A value is reinterpreted if the
 102 // cast instruction would cause the underlying bits to change.
 103 //
 104 static inline bool isReinterpretingCast(const CastInst *CI) {
 105   return !losslessCastableTypes(CI->getOperand(0)->getType(), CI->getType());
 106 }
 107
 108
 109 // getPointedToStruct - If the argument is a pointer type, and the pointed to
 110 // value is a struct type, return the struct type, else return null.
 111 //
 112 static const StructType *getPointedToStruct(const Type *Ty) {
 113   const PointerType *PT = dyn_cast<PointerType>(Ty);
 114   return PT ? dyn_cast<StructType>(PT->getValueType()) : 0;
 115 }
 116
 117
 118 // getStructOffsetType - Return a vector of offsets that are to be used to index
 119 // into the specified struct type to get as close as possible to index as we
 120 // can.  Note that it is possible that we cannot get exactly to Offset, in which
 121 // case we update offset to be the offset we actually obtained.  The resultant
 122 // leaf type is returned.
 123 //
 124 static const Type *getStructOffsetType(const Type *Ty, unsigned &Offset,
 125                                        vector<ConstPoolVal*> &Offsets) {
 126   if (!isa<StructType>(Ty)) {
 127     Offset = 0;   // Return the offset that we were able to acheive
 128     return Ty;    // Return the leaf type
 129   }
 130
 131   assert(Offset < TD.getTypeSize(Ty) && "Offset not in struct!");
 132   const StructType *STy = cast<StructType>(Ty);
 133   const StructLayout *SL = TD.getStructLayout(STy);
 134
 135   // This loop terminates always on a 0 <= i < MemberOffsets.size()
 136   unsigned i;
 137   for (i = 0; i < SL->MemberOffsets.size()-1; ++i)
 138     if (Offset >= SL->MemberOffsets[i] && Offset <  SL->MemberOffsets[i+1])
 139       break;
 140
 141   assert(Offset >= SL->MemberOffsets[i] &&
 142          (i == SL->MemberOffsets.size()-1 || Offset <  SL->MemberOffsets[i+1]));
 143
 144   // Make sure to save the current index...
 145   Offsets.push_back(ConstPoolUInt::get(Type::UByteTy, i));
 146
 147   unsigned SubOffs = Offset - SL->MemberOffsets[i];
 148   const Type *LeafTy = getStructOffsetType(STy->getElementTypes()[i], SubOffs,
 149                                            Offsets);
 150   Offset = SL->MemberOffsets[i] + SubOffs;
 151   return LeafTy;
 152 }
 153
 154
 155
 156 // ReplaceInstWithValue - Replace all uses of an instruction (specified by BI)
 157 // with a value, then remove and delete the original instruction.
 158 //
 159 static void ReplaceInstWithValue(BasicBlock::InstListType &BIL,
 160                                  BasicBlock::iterator &BI, Value *V) {
 161   Instruction *I = *BI;
 162   // Replaces all of the uses of the instruction with uses of the value
 163   I->replaceAllUsesWith(V);
 164
 165   // Remove the unneccesary instruction now...
 166   BIL.remove(BI);
 167
 168   // Make sure to propogate a name if there is one already...
 169   if (I->hasName() && !V->hasName())
 170     V->setName(I->getName(), BIL.getParent()->getSymbolTable());
 171
 172   // Remove the dead instruction now...
 173   delete I;
 174 }
 175
 176
 177 // ReplaceInstWithInst - Replace the instruction specified by BI with the
 178 // instruction specified by I.  The original instruction is deleted and BI is
 179 // updated to point to the new instruction.
 180 //
 181 static void ReplaceInstWithInst(BasicBlock::InstListType &BIL,
 182                                 BasicBlock::iterator &BI, Instruction *I) {
 183   assert(I->getParent() == 0 &&
 184          "ReplaceInstWithInst: Instruction already inserted into basic block!");
 185
 186   // Insert the new instruction into the basic block...
 187   BI = BIL.insert(BI, I)+1;
 188
 189   // Replace all uses of the old instruction, and delete it.
 190   ReplaceInstWithValue(BIL, BI, I);
 191
 192   // Reexamine the instruction just inserted next time around the cleanup pass
 193   // loop.
 194   --BI;
 195 }
 196
 197
 198
 199 typedef map<const Value*, const Type*> ValueTypeCache;
 200 typedef map<const Value*, Value*>      ValueMapCache;
 201
 202
 203
 204 // ExpressionConvertableToType - Return true if it is possible
 205 static bool ExpressionConvertableToType(Value *V, const Type *Ty) {
 206   Instruction *I = dyn_cast<Instruction>(V);
 207   if (I == 0) {
 208     // It's not an instruction, check to see if it's a constant... all constants
 209     // can be converted to an equivalent value (except pointers, they can't be
 210     // const prop'd in general).
 211     //
 212     if (isa<ConstPoolVal>(V) &&
 213         !isa<PointerType>(V->getType()) && !isa<PointerType>(Ty)) return true;
 214
 215     return false;              // Otherwise, we can't convert!
 216   }
 217   if (I->getType() == Ty) return false;  // Expression already correct type!
 218
 219   switch (I->getOpcode()) {
 220   case Instruction::Cast:
 221     // We can convert the expr if the cast destination type is losslessly
 222     // convertable to the requested type.
 223     return losslessCastableTypes(Ty, I->getType());
 224
 225   case Instruction::Add:
 226   case Instruction::Sub:
 227     return ExpressionConvertableToType(I->getOperand(0), Ty) &&
 228            ExpressionConvertableToType(I->getOperand(1), Ty);
 229   case Instruction::Shr:
 230     if (Ty->isSigned() != V->getType()->isSigned()) return false;
 231     // FALL THROUGH
 232   case Instruction::Shl:
 233     return ExpressionConvertableToType(I->getOperand(0), Ty);
 234
 235   case Instruction::Load: {
 236     LoadInst *LI = cast<LoadInst>(I);
 237     if (LI->hasIndices()) return false;
 238     return ExpressionConvertableToType(LI->getPtrOperand(),
 239                                        PointerType::get(Ty));
 240   }
 241   case Instruction::GetElementPtr: {
 242     // GetElementPtr's are directly convertable to a pointer type if they have
 243     // a number of zeros at the end.  Because removing these values does not
 244     // change the logical offset of the GEP, it is okay and fair to remove them.
 245     // This can change this:
 246     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 247     //   %t2 = cast %List * * %t1 to %List *
 248     // into
 249     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 250     //
 251     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 252     const PointerType *PTy = dyn_cast<PointerType>(Ty);
 253     if (!PTy) return false;
 254
 255     // Check to see if there are zero elements that we can remove from the
 256     // index array.  If there are, check to see if removing them causes us to
 257     // get to the right type...
 258     //
 259     vector<ConstPoolVal*> Indices = GEP->getIndices();
 260     const Type *BaseType = GEP->getPtrOperand()->getType();
 261
 262     while (Indices.size() &&
 263            cast<ConstPoolUInt>(Indices.back())->getValue() == 0) {
 264       Indices.pop_back();
 265       const Type *ElTy = GetElementPtrInst::getIndexedType(BaseType, Indices,
 266                                                            true);
 267       if (ElTy == PTy->getValueType())
 268         return true;  // Found a match!!
 269     }
 270     break;   // No match, maybe next time.
 271   }
 272   }
 273   return false;
 274 }
 275
 276
 277 static Value *ConvertExpressionToType(Value *V, const Type *Ty) {
 278   assert(ExpressionConvertableToType(V, Ty) && "Value is not convertable!");
 279   Instruction *I = dyn_cast<Instruction>(V);
 280   if (I == 0)
 281     if (ConstPoolVal *CPV = cast<ConstPoolVal>(V)) {
 282       // Constants are converted by constant folding the cast that is required.
 283       // We assume here that all casts are implemented for constant prop.
 284       Value *Result = opt::ConstantFoldCastInstruction(CPV, Ty);
 285       if (!Result) cerr << "Couldn't fold " << CPV << " to " << Ty << endl;
 286       assert(Result && "ConstantFoldCastInstruction Failed!!!");
 287       return Result;
 288     }
 289
 290
 291   BasicBlock *BB = I->getParent();
 292   BasicBlock::InstListType &BIL = BB->getInstList();
 293   string Name = I->getName();  if (!Name.empty()) I->setName("");
 294   Instruction *Res;     // Result of conversion
 295
 296   //cerr << endl << endl << "Type:\t" << Ty << "\nInst: " << I << "BB Before: " << BB << endl;
 297
 298   switch (I->getOpcode()) {
 299   case Instruction::Cast:
 300     Res = new CastInst(I->getOperand(0), Ty, Name);
 301     break;
 302
 303   case Instruction::Add:
 304   case Instruction::Sub:
 305     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
 306                                  ConvertExpressionToType(I->getOperand(0), Ty),
 307                                  ConvertExpressionToType(I->getOperand(1), Ty),
 308                                  Name);
 309     break;
 310
 311   case Instruction::Shl:
 312   case Instruction::Shr:
 313     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(),
 314                         ConvertExpressionToType(I->getOperand(0), Ty),
 315                         I->getOperand(1), Name);
 316     break;
 317
 318   case Instruction::Load: {
 319     LoadInst *LI = cast<LoadInst>(I);
 320     assert(!LI->hasIndices());
 321     Res = new LoadInst(ConvertExpressionToType(LI->getPtrOperand(),
 322                                                PointerType::get(Ty)), Name);
 323     break;
 324   }
 325
 326   case Instruction::GetElementPtr: {
 327     // GetElementPtr's are directly convertable to a pointer type if they have
 328     // a number of zeros at the end.  Because removing these values does not
 329     // change the logical offset of the GEP, it is okay and fair to remove them.
 330     // This can change this:
 331     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 332     //   %t2 = cast %List * * %t1 to %List *
 333     // into
 334     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 335     //
 336     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 337
 338     // Check to see if there are zero elements that we can remove from the
 339     // index array.  If there are, check to see if removing them causes us to
 340     // get to the right type...
 341     //
 342     vector<ConstPoolVal*> Indices = GEP->getIndices();
 343     const Type *BaseType = GEP->getPtrOperand()->getType();
 344     const Type *PVTy = cast<PointerType>(Ty)->getValueType();
 345     Res = 0;
 346     while (Indices.size() &&
 347            cast<ConstPoolUInt>(Indices.back())->getValue() == 0) {
 348       Indices.pop_back();
 349       if (GetElementPtrInst::getIndexedType(BaseType, Indices, true) == PVTy) {
 350         if (Indices.size() == 0) {
 351           Res = new CastInst(GEP->getPtrOperand(), BaseType); // NOOP
 352         } else {
 353           Res = new GetElementPtrInst(GEP->getPtrOperand(), Indices, Name);
 354         }
 355         break;
 356       }
 357     }
 358     assert(Res && "Didn't find match!");
 359     break;   // No match, maybe next time.
 360   }
 361
 362   default:
 363     assert(0 && "Expression convertable, but don't know how to convert?");
 364     return 0;
 365   }
 366
 367   BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 368   assert(It != BIL.end() && "Instruction not in own basic block??");
 369   BIL.insert(It, Res);
 370
 371   //cerr << "RInst: " << Res << "BB After: " << BB << endl << endl;
 372
 373   return Res;
 374 }
 375
 376 static inline const Type *getTy(const Value *V, ValueTypeCache &CT) {
 377   ValueTypeCache::iterator I = CT.find(V);
 378   if (I == CT.end()) return V->getType();
 379   return I->second;
 380 }
 381
 382
 383 static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
 384                                      ValueTypeCache &ConvertedTypes);
 385
 386 // RetValConvertableToType - Return true if it is possible
 387 static bool RetValConvertableToType(Value *V, const Type *Ty,
 388                                     ValueTypeCache &ConvertedTypes) {
 389   ValueTypeCache::iterator I = ConvertedTypes.find(V);
 390   if (I != ConvertedTypes.end()) return I->second == Ty;
 391   ConvertedTypes[V] = Ty;
 392
 393   // It is safe to convert the specified value to the specified type IFF all of
 394   // the uses of the value can be converted to accept the new typed value.
 395   //
 396   for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I)
 397     if (!OperandConvertableToType(*I, V, Ty, ConvertedTypes))
 398       return false;
 399
 400   return true;
 401 }
 402
 403
 404 // OperandConvertableToType - Return true if it is possible to convert operand
 405 // V of User (instruction) U to the specified type.  This is true iff it is
 406 // possible to change the specified instruction to accept this.  CTMap is a map
 407 // of converted types, so that circular definitions will see the future type of
 408 // the expression, not the static current type.
 409 //
 410 static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
 411                                      ValueTypeCache &CTMap) {
 412   assert(V->getType() != Ty &&
 413          "OperandConvertableToType: Operand is already right type!");
 414   Instruction *I = dyn_cast<Instruction>(U);
 415   if (I == 0) return false;              // We can't convert!
 416
 417   switch (I->getOpcode()) {
 418   case Instruction::Cast:
 419     assert(I->getOperand(0) == V);
 420     // We can convert the expr if the cast destination type is losslessly
 421     // convertable to the requested type.
 422     return losslessCastableTypes(Ty, I->getOperand(0)->getType());
 423
 424   case Instruction::Add:
 425   case Instruction::Sub: {
 426     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
 427     return RetValConvertableToType(I, Ty, CTMap) &&
 428            ExpressionConvertableToType(OtherOp, Ty);
 429   }
 430   case Instruction::SetEQ:
 431   case Instruction::SetNE: {
 432     Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0);
 433     return ExpressionConvertableToType(OtherOp, Ty);
 434   }
 435   case Instruction::Shr:
 436     if (Ty->isSigned() != V->getType()->isSigned()) return false;
 437     // FALL THROUGH
 438   case Instruction::Shl:
 439     assert(I->getOperand(0) == V);
 440     return RetValConvertableToType(I, Ty, CTMap);
 441
 442   case Instruction::Load:
 443     assert(I->getOperand(0) == V);
 444     if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
 445       LoadInst *LI = cast<LoadInst>(I);
 446       if (LI->hasIndices() ||
 447           TD.getTypeSize(PT->getValueType()) != TD.getTypeSize(LI->getType()))
 448         return false;
 449
 450       return RetValConvertableToType(LI, PT->getValueType(), CTMap);
 451     }
 452     return false;
 453
 454   case Instruction::Store: {
 455     StoreInst *SI = cast<StoreInst>(I);
 456     if (SI->hasIndices()) return false;
 457
 458     if (V == I->getOperand(0)) {
 459       // Can convert the store if we can convert the pointer operand to match
 460       // the new  value type...
 461       return ExpressionConvertableToType(I->getOperand(1),PointerType::get(Ty));
 462     } else if (const PointerType *PT = dyn_cast<PointerType>(Ty)) {
 463       if (isa<ArrayType>(PT->getValueType()))
 464         return false;  // Avoid getDataSize on unsized array type!
 465       assert(V == I->getOperand(1));
 466
 467       // Must move the same amount of data...
 468       if (TD.getTypeSize(PT->getValueType()) !=
 469           TD.getTypeSize(I->getOperand(0)->getType())) return false;
 470
 471       // Can convert store if the incoming value is convertable...
 472       return ExpressionConvertableToType(I->getOperand(0), PT->getValueType());
 473     }
 474     return false;
 475   }
 476
 477
 478 #if 0
 479   case Instruction::GetElementPtr: {
 480     // GetElementPtr's are directly convertable to a pointer type if they have
 481     // a number of zeros at the end.  Because removing these values does not
 482     // change the logical offset of the GEP, it is okay and fair to remove them.
 483     // This can change this:
 484     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 485     //   %t2 = cast %List * * %t1 to %List *
 486     // into
 487     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 488     //
 489     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 490     const PointerType *PTy = dyn_cast<PointerType>(Ty);
 491     if (!PTy) return false;
 492
 493     // Check to see if there are zero elements that we can remove from the
 494     // index array.  If there are, check to see if removing them causes us to
 495     // get to the right type...
 496     //
 497     vector<ConstPoolVal*> Indices = GEP->getIndices();
 498     const Type *BaseType = GEP->getPtrOperand()->getType();
 499
 500     while (Indices.size() &&
 501            cast<ConstPoolUInt>(Indices.back())->getValue() == 0) {
 502       Indices.pop_back();
 503       const Type *ElTy = GetElementPtrInst::getIndexedType(BaseType, Indices,
 504                                                            true);
 505       if (ElTy == PTy->getValueType())
 506         return true;  // Found a match!!
 507     }
 508     break;   // No match, maybe next time.
 509   }
 510 #endif
 511   }
 512   return false;
 513 }
 514
 515
 516
 517
 518
 519
 520 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
 521                                  ValueMapCache &VMC);
 522
 523 // RetValConvertableToType - Return true if it is possible
 524 static void ConvertUsersType(Value *V, Value *NewVal, ValueMapCache &VMC) {
 525
 526   // It is safe to convert the specified value to the specified type IFF all of
 527   // the uses of the value can be converted to accept the new typed value.
 528   //
 529   while (!V->use_empty()) {
 530     unsigned OldSize = V->use_size();
 531     ConvertOperandToType(V->use_back(), V, NewVal, VMC);
 532     assert(V->use_size() != OldSize && "Use didn't detatch from value!");
 533   }
 534 }
 535
 536
 537
 538 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
 539                                  ValueMapCache &VMC) {
 540   Instruction *I = cast<Instruction>(U);  // Only Instructions convertable
 541
 542   BasicBlock *BB = I->getParent();
 543   BasicBlock::InstListType &BIL = BB->getInstList();
 544   string Name = I->getName();  if (!Name.empty()) I->setName("");
 545   Instruction *Res;     // Result of conversion
 546
 547   //cerr << endl << endl << "Type:\t" << Ty << "\nInst: " << I << "BB Before: " << BB << endl;
 548
 549   switch (I->getOpcode()) {
 550   case Instruction::Cast:
 551     assert(I->getOperand(0) == OldVal);
 552     Res = new CastInst(NewVal, I->getType(), Name);
 553     break;
 554
 555   case Instruction::Add:
 556   case Instruction::Sub:
 557   case Instruction::SetEQ:
 558   case Instruction::SetNE: {
 559     unsigned OtherIdx = (OldVal == I->getOperand(0)) ? 1 : 0;
 560     Value *OtherOp    = I->getOperand(OtherIdx);
 561     Value *NewOther   = ConvertExpressionToType(OtherOp, NewVal->getType());
 562
 563     Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(),
 564                                  OtherIdx == 0 ? NewOther : NewVal,
 565                                  OtherIdx == 1 ? NewOther : NewVal,
 566                                  Name);
 567     break;
 568   }
 569   case Instruction::Shl:
 570   case Instruction::Shr:
 571     assert(I->getOperand(0) == OldVal);
 572     Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), NewVal,
 573                         I->getOperand(1), Name);
 574     break;
 575
 576   case Instruction::Load:
 577     assert(I->getOperand(0) == OldVal);
 578     Res = new LoadInst(NewVal, Name);
 579     break;
 580
 581   case Instruction::Store: {
 582     if (I->getOperand(0) == OldVal) {  // Replace the source value
 583       Value *NewPtr =
 584         ConvertExpressionToType(I->getOperand(1),
 585                                 PointerType::get(NewVal->getType()));
 586       Res = new StoreInst(NewVal, NewPtr);
 587     } else {                           // Replace the source pointer
 588       const Type *ValType =cast<PointerType>(NewVal->getType())->getValueType();
 589       Value *NewV = ConvertExpressionToType(I->getOperand(0), ValType);
 590       Res = new StoreInst(NewV, NewVal);
 591     }
 592     break;
 593   }
 594
 595 #if 0
 596   case Instruction::GetElementPtr: {
 597     // GetElementPtr's are directly convertable to a pointer type if they have
 598     // a number of zeros at the end.  Because removing these values does not
 599     // change the logical offset of the GEP, it is okay and fair to remove them.
 600     // This can change this:
 601     //   %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0  ; <%List **>
 602     //   %t2 = cast %List * * %t1 to %List *
 603     // into
 604     //   %t2 = getelementptr %Hosp * %hosp, ubyte 4           ; <%List *>
 605     //
 606     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
 607
 608     // Check to see if there are zero elements that we can remove from the
 609     // index array.  If there are, check to see if removing them causes us to
 610     // get to the right type...
 611     //
 612     vector<ConstPoolVal*> Indices = GEP->getIndices();
 613     const Type *BaseType = GEP->getPtrOperand()->getType();
 614     const Type *PVTy = cast<PointerType>(Ty)->getValueType();
 615     Res = 0;
 616     while (Indices.size() &&
 617            cast<ConstPoolUInt>(Indices.back())->getValue() == 0) {
 618       Indices.pop_back();
 619       if (GetElementPtrInst::getIndexedType(BaseType, Indices, true) == PVTy) {
 620         if (Indices.size() == 0) {
 621           Res = new CastInst(GEP->getPtrOperand(), BaseType); // NOOP
 622         } else {
 623           Res = new GetElementPtrInst(GEP->getPtrOperand(), Indices, Name);
 624         }
 625         break;
 626       }
 627     }
 628     assert(Res && "Didn't find match!");
 629     break;   // No match, maybe next time.
 630   }
 631 #endif
 632
 633   default:
 634     assert(0 && "Expression convertable, but don't know how to convert?");
 635     return;
 636   }
 637
 638   BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
 639   assert(It != BIL.end() && "Instruction not in own basic block??");
 640   BIL.insert(It, Res);   // Keep It pointing to old instruction
 641
 642 #if DEBUG_PEEPHOLE_INSTS
 643   cerr << "In: " << I << "Out: " << Res;
 644 #endif
 645
 646   //cerr << "RInst: " << Res << "BB After: " << BB << endl << endl;
 647
 648   if (I->getType() != Res->getType())
 649     ConvertUsersType(I, Res, VMC);
 650   else
 651     I->replaceAllUsesWith(Res);
 652
 653   // Now we just need to remove the old instruction so we don't get infinite
 654   // loops.  Note that we cannot use DCE because DCE won't remove a store
 655   // instruction, for example.
 656   assert(I->use_size() == 0 && "Uses of Instruction remain!!!");
 657
 658   It = find(BIL.begin(), BIL.end(), I);
 659   assert(It != BIL.end() && "Instruction no longer in basic block??");
 660   delete BIL.remove(It);
 661 }
 662
 663
 664
 665
 666
 667
 668
 669
 670
 671
 672
 673
 674
 675
 676 // DoInsertArrayCast - If the argument value has a pointer type, and if the
 677 // argument value is used as an array, insert a cast before the specified
 678 // basic block iterator that casts the value to an array pointer.  Return the
 679 // new cast instruction (in the CastResult var), or null if no cast is inserted.
 680 //
 681 static bool DoInsertArrayCast(Method *CurMeth, Value *V, BasicBlock *BB,
 682                               BasicBlock::iterator &InsertBefore,
 683                               CastInst *&CastResult) {
 684   const PointerType *ThePtrType = dyn_cast<PointerType>(V->getType());
 685   if (!ThePtrType) return false;
 686   bool InsertCast = false;
 687
 688   for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I) {
 689     Instruction *Inst = cast<Instruction>(*I);
 690     switch (Inst->getOpcode()) {
 691     default: break;                  // Not an interesting use...
 692     case Instruction::Add:           // It's being used as an array index!
 693   //case Instruction::Sub:
 694       InsertCast = true;
 695       break;
 696     case Instruction::Cast:          // There is already a cast instruction!
 697       if (const PointerType *PT = dyn_cast<const PointerType>(Inst->getType()))
 698         if (const ArrayType *AT = dyn_cast<const ArrayType>(PT->getValueType()))
 699           if (AT->getElementType() == ThePtrType->getValueType()) {
 700             // Cast already exists! Return the existing one!
 701             CastResult = cast<CastInst>(Inst);
 702             return false;       // No changes made to program though...
 703           }
 704       break;
 705     }
 706   }
 707
 708   if (!InsertCast) return false;  // There is no reason to insert a cast!
 709
 710   // Insert a cast!
 711   const Type *ElTy = ThePtrType->getValueType();
 712   const PointerType *DestTy = PointerType::get(ArrayType::get(ElTy));
 713
 714   CastResult = new CastInst(V, DestTy);
 715   BB->getInstList().insert(InsertBefore, CastResult);
 716   //cerr << "Inserted cast: " << CastResult;
 717   return true;            // Made a change!
 718 }
 719
 720
 721 // DoInsertArrayCasts - Loop over all "incoming" values in the specified method,
 722 // inserting a cast for pointer values that are used as arrays. For our
 723 // purposes, an incoming value is considered to be either a value that is
 724 // either a method parameter, a value created by alloca or malloc, or a value
 725 // returned from a function call.  All casts are kept attached to their original
 726 // values through the PtrCasts map.
 727 //
 728 static bool DoInsertArrayCasts(Method *M, map<Value*, CastInst*> &PtrCasts) {
 729   assert(!M->isExternal() && "Can't handle external methods!");
 730
 731   // Insert casts for all arguments to the function...
 732   bool Changed = false;
 733   BasicBlock *CurBB = M->front();
 734   BasicBlock::iterator It = CurBB->begin();
 735   for (Method::ArgumentListType::iterator AI = M->getArgumentList().begin(),
 736          AE = M->getArgumentList().end(); AI != AE; ++AI) {
 737     CastInst *TheCast = 0;
 738     if (DoInsertArrayCast(M, *AI, CurBB, It, TheCast)) {
 739       It = CurBB->begin();      // We might have just invalidated the iterator!
 740       Changed = true;           // Yes we made a change
 741       ++It;                     // Insert next cast AFTER this one...
 742     }
 743
 744     if (TheCast)                // Is there a cast associated with this value?
 745       PtrCasts[*AI] = TheCast;  // Yes, add it to the map...
 746   }
 747
 748   // TODO: insert casts for alloca, malloc, and function call results.  Also,
 749   // look for pointers that already have casts, to add to the map.
 750
 751   return Changed;
 752 }
 753
 754
 755
 756
 757 // DoElminatePointerArithmetic - Loop over each incoming pointer variable,
 758 // replacing indexing arithmetic with getelementptr calls.
 759 //
 760 static bool DoEliminatePointerArithmetic(const pair<Value*, CastInst*> &Val) {
 761   Value    *V  = Val.first;   // The original pointer
 762   CastInst *CV = Val.second;  // The array casted version of the pointer...
 763
 764   for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I) {
 765     Instruction *Inst = cast<Instruction>(*I);
 766     if (Inst->getOpcode() != Instruction::Add)
 767       continue;   // We only care about add instructions
 768
 769     BinaryOperator *Add = cast<BinaryOperator>(Inst);
 770
 771     // Make sure the array is the first operand of the add expression...
 772     if (Add->getOperand(0) != V)
 773       Add->swapOperands();
 774
 775     // Get the amount added to the pointer value...
 776     Value *AddAmount = Add->getOperand(1);
 777
 778
 779   }
 780   return false;
 781 }
 782
 783
 784 // Peephole Malloc instructions: we take a look at the use chain of the
 785 // malloc instruction, and try to find out if the following conditions hold:
 786 //   1. The malloc is of the form: 'malloc [sbyte], uint <constant>'
 787 //   2. The only users of the malloc are cast instructions
 788 //   3. Of the cast instructions, there is only one destination pointer type
 789 //      [RTy] where the size of the pointed to object is equal to the number
 790 //      of bytes allocated.
 791 //
 792 // If these conditions hold, we convert the malloc to allocate an [RTy]
 793 // element.  This should be extended in the future to handle arrays. TODO
 794 //
 795 static bool PeepholeMallocInst(BasicBlock *BB, BasicBlock::iterator &BI) {
 796   MallocInst *MI = cast<MallocInst>(*BI);
 797   if (!MI->isArrayAllocation()) return false;    // No array allocation?
 798
 799   ConstPoolUInt *Amt = dyn_cast<ConstPoolUInt>(MI->getArraySize());
 800   if (Amt == 0 || MI->getAllocatedType() != ArrayType::get(Type::SByteTy))
 801     return false;
 802
 803   // Get the number of bytes allocated...
 804   unsigned Size = Amt->getValue();
 805   const Type *ResultTy = 0;
 806
 807   // Loop over all of the uses of the malloc instruction, inspecting casts.
 808   for (Value::use_iterator I = MI->use_begin(), E = MI->use_end();
 809        I != E; ++I) {
 810     if (!isa<CastInst>(*I)) {
 811       //cerr << "\tnon" << *I;
 812       return false;  // A non cast user?
 813     }
 814     CastInst *CI = cast<CastInst>(*I);
 815     //cerr << "\t" << CI;
 816
 817     // We only work on casts to pointer types for sure, be conservative
 818     if (!isa<PointerType>(CI->getType())) {
 819       cerr << "Found cast of malloc value to non pointer type:\n" << CI;
 820       return false;
 821     }
 822
 823     const Type *DestTy = cast<PointerType>(CI->getType())->getValueType();
 824     if (TD.getTypeSize(DestTy) == Size && DestTy != ResultTy) {
 825       // Does the size of the allocated type match the number of bytes
 826       // allocated?
 827       //
 828       if (ResultTy == 0) {
 829         ResultTy = DestTy;   // Keep note of this for future uses...
 830       } else {
 831         // It's overdefined!  We don't know which type to convert to!
 832         return false;
 833       }
 834     }
 835   }
 836
 837   // If we get this far, we have either found, or not, a type that is cast to
 838   // that is of the same size as the malloc instruction.
 839   if (!ResultTy) return false;
 840
 841   PRINT_PEEPHOLE1("mall-refine:in ", MI);
 842   ReplaceInstWithInst(BB->getInstList(), BI,
 843                       MI = new MallocInst(PointerType::get(ResultTy)));
 844   PRINT_PEEPHOLE1("mall-refine:out", MI);
 845   return true;
 846 }
 847
 848
 849 // Peephole optimize the following instructions:
 850 //   %t1 = cast int (uint) * %reg111 to uint (...) *
 851 //   %t2 = call uint (...) * %cast111( uint %key )
 852 //
 853 // Into: %t3 = call int (uint) * %reg111( uint %key )
 854 //       %t2 = cast int %t3 to uint
 855 //
 856 static bool PeepholeCallInst(BasicBlock *BB, BasicBlock::iterator &BI) {
 857   CallInst *CI = cast<CallInst>(*BI);
 858   return false;
 859 }
 860
 861
 862 static bool PeepholeOptimize(BasicBlock *BB, BasicBlock::iterator &BI) {
 863   Instruction *I = *BI;
 864
 865   if (CastInst *CI = dyn_cast<CastInst>(I)) {
 866     Value       *Src    = CI->getOperand(0);
 867     Instruction *SrcI   = dyn_cast<Instruction>(Src); // Nonnull if instr source
 868     const Type  *DestTy = CI->getType();
 869
 870     // Peephole optimize the following instruction:
 871     // %V2 = cast <ty> %V to <ty>
 872     //
 873     // Into: <nothing>
 874     //
 875     if (DestTy == Src->getType()) {   // Check for a cast to same type as src!!
 876       PRINT_PEEPHOLE1("cast-of-self-ty", CI);
 877       CI->replaceAllUsesWith(Src);
 878       if (!Src->hasName() && CI->hasName()) {
 879         string Name = CI->getName();
 880         CI->setName("");
 881         Src->setName(Name, BB->getParent()->getSymbolTable());
 882       }
 883       return true;
 884     }
 885
 886     // Peephole optimize the following instructions:
 887     // %tmp = cast <ty> %V to <ty2>
 888     // %V  = cast <ty2> %tmp to <ty3>     ; Where ty & ty2 are same size
 889     //
 890     // Into: cast <ty> %V to <ty3>
 891     //
 892     if (SrcI)
 893       if (CastInst *CSrc = dyn_cast<CastInst>(SrcI))
 894         if (isReinterpretingCast(CI) + isReinterpretingCast(CSrc) < 2) {
 895           // We can only do c-c elimination if, at most, one cast does a
 896           // reinterpretation of the input data.
 897           //
 898           // If legal, make this cast refer the the original casts argument!
 899           //
 900           PRINT_PEEPHOLE2("cast-cast:in ", CI, CSrc);
 901           CI->setOperand(0, CSrc->getOperand(0));
 902           PRINT_PEEPHOLE1("cast-cast:out", CI);
 903           return true;
 904         }
 905
 906     // Check to see if it's a cast of an instruction that does not depend on the
 907     // specific type of the operands to do it's job.
 908     if (!isReinterpretingCast(CI)) {
 909       ValueTypeCache ConvertedTypes;
 910       if (RetValConvertableToType(CI, Src->getType(), ConvertedTypes)) {
 911         PRINT_PEEPHOLE2("EXPR-CONV:in ", CI, Src);
 912
 913         ValueMapCache ValueMap;
 914         ConvertUsersType(CI, Src, ValueMap);
 915         if (!Src->hasName() && CI->hasName()) {
 916           string Name = CI->getName(); CI->setName("");
 917           Src->setName(Name, BB->getParent()->getSymbolTable());
 918         }
 919         BI = BB->begin();  // Rescan basic block.  BI might be invalidated.
 920         PRINT_PEEPHOLE1("EXPR-CONV:out", I);
 921         return true;
 922       }
 923     }
 924
 925     // Check to see if we are casting from a structure pointer to a pointer to
 926     // the first element of the structure... to avoid munching other peepholes,
 927     // we only let this happen if there are no add uses of the cast.
 928     //
 929     // Peephole optimize the following instructions:
 930     // %t1 = cast {<...>} * %StructPtr to <ty> *
 931     //
 932     // Into: %t2 = getelementptr {<...>} * %StructPtr, <0, 0, 0, ...>
 933     //       %t1 = cast <eltype> * %t1 to <ty> *
 934     //
 935     if (const StructType *STy = getPointedToStruct(Src->getType()))
 936       if (const PointerType *DestPTy = dyn_cast<PointerType>(DestTy)) {
 937
 938         // Loop over uses of the cast, checking for add instructions.  If an add
 939         // exists, this is probably a part of a more complex GEP, so we don't
 940         // want to mess around with the cast.
 941         //
 942         bool HasAddUse = false;
 943         for (Value::use_iterator I = CI->use_begin(), E = CI->use_end();
 944              I != E; ++I)
 945           if (isa<Instruction>(*I) &&
 946               cast<Instruction>(*I)->getOpcode() == Instruction::Add) {
 947             HasAddUse = true; break;
 948           }
 949
 950         // If it doesn't have an add use, check to see if the dest type is
 951         // losslessly convertable to one of the types in the start of the struct
 952         // type.
 953         //
 954         if (!HasAddUse) {
 955           const Type *DestPointedTy = DestPTy->getValueType();
 956           unsigned Depth = 1;
 957           const StructType *CurSTy = STy;
 958           const Type *ElTy = 0;
 959           while (CurSTy) {
 960
 961             // Check for a zero element struct type... if we have one, bail.
 962             if (CurSTy->getElementTypes().size() == 0) break;
 963
 964             // Grab the first element of the struct type, which must lie at
 965             // offset zero in the struct.
 966             //
 967             ElTy = CurSTy->getElementTypes()[0];
 968
 969             // Did we find what we're looking for?
 970             if (losslessCastableTypes(ElTy, DestPointedTy)) break;
 971
 972             // Nope, go a level deeper.
 973             ++Depth;
 974             CurSTy = dyn_cast<StructType>(ElTy);
 975             ElTy = 0;
 976           }
 977
 978           // Did we find what we were looking for? If so, do the transformation
 979           if (ElTy) {
 980             PRINT_PEEPHOLE1("cast-for-first:in", CI);
 981
 982             // Build the index vector, full of all zeros
 983             vector<ConstPoolVal *> Indices(Depth,
 984                                            ConstPoolUInt::get(Type::UByteTy,0));
 985
 986             // Insert the new T cast instruction... stealing old T's name
 987             GetElementPtrInst *GEP = new GetElementPtrInst(Src, Indices,
 988                                                            CI->getName());
 989             CI->setName("");
 990             BI = BB->getInstList().insert(BI, GEP)+1;
 991
 992             // Make the old cast instruction reference the new GEP instead of
 993             // the old src value.
 994             //
 995             CI->setOperand(0, GEP);
 996
 997             PRINT_PEEPHOLE2("cast-for-first:out", GEP, CI);
 998             return true;
 999           }
1000         }
1001       }
1002
1003
1004   } else if (MallocInst *MI = dyn_cast<MallocInst>(I)) {
1005     if (PeepholeMallocInst(BB, BI)) return true;
1006
1007   } else if (CallInst *CI = dyn_cast<CallInst>(I)) {
1008     if (PeepholeCallInst(BB, BI)) return true;
1009
1010   } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
1011     Value *Val     = SI->getOperand(0);
1012     Value *Pointer = SI->getPtrOperand();
1013
1014     // Peephole optimize the following instructions:
1015     // %t1 = getelementptr {<...>} * %StructPtr, <element indices>
1016     // store <elementty> %v, <elementty> * %t1
1017     //
1018     // Into: store <elementty> %v, {<...>} * %StructPtr, <element indices>
1019     //
1020     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Pointer)) {
1021       PRINT_PEEPHOLE2("gep-store:in", GEP, SI);
1022       ReplaceInstWithInst(BB->getInstList(), BI,
1023                           SI = new StoreInst(Val, GEP->getPtrOperand(),
1024                                              GEP->getIndices()));
1025       PRINT_PEEPHOLE1("gep-store:out", SI);
1026       return true;
1027     }
1028
1029     // Peephole optimize the following instructions:
1030     // %t = cast <T1>* %P to <T2> * ;; If T1 is losslessly convertable to T2
1031     // store <T2> %V, <T2>* %t
1032     //
1033     // Into:
1034     // %t = cast <T2> %V to <T1>
1035     // store <T1> %t2, <T1>* %P
1036     //
1037     if (CastInst *CI = dyn_cast<CastInst>(Pointer))
1038       if (Value *CastSrc = CI->getOperand(0)) // CSPT = CastSrcPointerType
1039         if (PointerType *CSPT = dyn_cast<PointerType>(CastSrc->getType()))
1040           if (losslessCastableTypes(Val->getType(), // convertable types!
1041                                     CSPT->getValueType()) &&
1042               !SI->hasIndices()) {      // No subscripts yet!
1043             PRINT_PEEPHOLE3("st-src-cast:in ", Pointer, Val, SI);
1044
1045             // Insert the new T cast instruction... stealing old T's name
1046             CastInst *NCI = new CastInst(Val, CSPT->getValueType(),
1047                                          CI->getName());
1048             CI->setName("");
1049             BI = BB->getInstList().insert(BI, NCI)+1;
1050
1051             // Replace the old store with a new one!
1052             ReplaceInstWithInst(BB->getInstList(), BI,
1053                                 SI = new StoreInst(NCI, CastSrc));
1054             PRINT_PEEPHOLE3("st-src-cast:out", NCI, CastSrc, SI);
1055             return true;
1056           }
1057
1058
1059   } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
1060     Value *Pointer = LI->getPtrOperand();
1061
1062     // Peephole optimize the following instructions:
1063     // %t1 = getelementptr {<...>} * %StructPtr, <element indices>
1064     // %V  = load <elementty> * %t1
1065     //
1066     // Into: load {<...>} * %StructPtr, <element indices>
1067     //
1068     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Pointer)) {
1069       PRINT_PEEPHOLE2("gep-load:in", GEP, LI);
1070       ReplaceInstWithInst(BB->getInstList(), BI,
1071                           LI = new LoadInst(GEP->getPtrOperand(),
1072                                             GEP->getIndices()));
1073       PRINT_PEEPHOLE1("gep-load:out", LI);
1074       return true;
1075     }
1076   } else if (I->getOpcode() == Instruction::Add &&
1077              isa<CastInst>(I->getOperand(1))) {
1078
1079     // Peephole optimize the following instructions:
1080     // %t1 = cast ulong <const int> to {<...>} *
1081     // %t2 = add {<...>} * %SP, %t1              ;; Constant must be 2nd operand
1082     //
1083     //    or
1084     // %t1 = cast {<...>}* %SP to int*
1085     // %t5 = cast ulong <const int> to int*
1086     // %t2 = add int* %t1, %t5                   ;; int is same size as field
1087     //
1088     // Into: %t3 = getelementptr {<...>} * %SP, <element indices>
1089     //       %t2 = cast <eltype> * %t3 to {<...>}*
1090     //
1091     Value            *AddOp1  = I->getOperand(0);
1092     CastInst         *AddOp2  = cast<CastInst>(I->getOperand(1));
1093     ConstPoolUInt    *OffsetV = dyn_cast<ConstPoolUInt>(AddOp2->getOperand(0));
1094     unsigned          Offset  = OffsetV ? OffsetV->getValue() : 0;
1095     Value            *SrcPtr;  // Of type pointer to struct...
1096     const StructType *StructTy;
1097
1098     if ((StructTy = getPointedToStruct(AddOp1->getType()))) {
1099       SrcPtr = AddOp1;                      // Handle the first case...
1100     } else if (CastInst *AddOp1c = dyn_cast<CastInst>(AddOp1)) {
1101       SrcPtr = AddOp1c->getOperand(0);      // Handle the second case...
1102       StructTy = getPointedToStruct(SrcPtr->getType());
1103     }
1104
1105     // Only proceed if we have detected all of our conditions successfully...
1106     if (Offset && StructTy && SrcPtr && Offset < TD.getTypeSize(StructTy)) {
1107       const StructLayout *SL = TD.getStructLayout(StructTy);
1108       vector<ConstPoolVal*> Offsets;
1109       unsigned ActualOffset = Offset;
1110       const Type *ElTy = getStructOffsetType(StructTy, ActualOffset, Offsets);
1111
1112       if (getPointedToStruct(AddOp1->getType())) {  // case 1
1113         PRINT_PEEPHOLE2("add-to-gep1:in", AddOp2, I);
1114       } else {
1115         PRINT_PEEPHOLE3("add-to-gep2:in", AddOp1, AddOp2, I);
1116       }
1117
1118       GetElementPtrInst *GEP = new GetElementPtrInst(SrcPtr, Offsets);
1119       BI = BB->getInstList().insert(BI, GEP)+1;
1120
1121       assert(Offset-ActualOffset == 0  &&
1122              "GEP to middle of element not implemented yet!");
1123
1124       ReplaceInstWithInst(BB->getInstList(), BI,
1125                           I = new CastInst(GEP, I->getType()));
1126       PRINT_PEEPHOLE2("add-to-gep:out", GEP, I);
1127       return true;
1128     }
1129   }
1130
1131   return false;
1132 }
1133
1134
1135
1136
1137 static bool DoRaisePass(Method *M) {
1138   bool Changed = false;
1139   for (Method::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI) {
1140     BasicBlock *BB = *MI;
1141     BasicBlock::InstListType &BIL = BB->getInstList();
1142
1143     for (BasicBlock::iterator BI = BB->begin(); BI != BB->end();) {
1144       if (opt::DeadCodeElimination::dceInstruction(BIL, BI) ||
1145           PeepholeOptimize(BB, BI))
1146         Changed = true;
1147       else
1148         ++BI;
1149     }
1150   }
1151   return Changed;
1152 }
1153
1154
1155 // RaisePointerReferences::doit - Raise a method representation to a higher
1156 // level.
1157 //
1158 bool RaisePointerReferences::doit(Method *M) {
1159   if (M->isExternal()) return false;
1160   bool Changed = false;
1161
1162 #ifdef DEBUG_PEEPHOLE_INSTS
1163   cerr << "\n\n\nStarting to work on Method '" << M->getName() << "'\n";
1164 #endif
1165
1166   while (DoRaisePass(M)) Changed = true;
1167
1168   // PtrCasts - Keep a mapping between the pointer values (the key of the
1169   // map), and the cast to array pointer (the value) in this map.  This is
1170   // used when converting pointer math into array addressing.
1171   //
1172   map<Value*, CastInst*> PtrCasts;
1173
1174   // Insert casts for all incoming pointer values.  Keep track of those casts
1175   // and the identified incoming values in the PtrCasts map.
1176   //
1177   Changed |= DoInsertArrayCasts(M, PtrCasts);
1178
1179   // Loop over each incoming pointer variable, replacing indexing arithmetic
1180   // with getelementptr calls.
1181   //
1182   Changed |= reduce_apply_bool(PtrCasts.begin(), PtrCasts.end(),
1183                                ptr_fun(DoEliminatePointerArithmetic));
1184
1185   return Changed;
1186 }