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