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 "TransformInternals.h"
  34 #include "llvm/Method.h"
  35 #include "llvm/Support/STLExtras.h"
  36 #include "llvm/iOther.h"
  37 #include "llvm/iMemory.h"
  38 #include "llvm/ConstPoolVals.h"
  39 #include "llvm/Optimizations/ConstantHandling.h"
  40 #include "llvm/Optimizations/DCE.h"
  41 #include <algorithm>
  42
  43 #include "llvm/Assembly/Writer.h"
  44
  45 //#define DEBUG_PEEPHOLE_INSTS 1
  46
  47 #ifdef DEBUG_PEEPHOLE_INSTS
  48 #define PRINT_PEEPHOLE(ID, NUM, I)            \
  49   cerr << "Inst P/H " << ID << "[" << NUM << "] " << I;
  50 #else
  51 #define PRINT_PEEPHOLE(ID, NUM, I)
  52 #endif
  53
  54 #define PRINT_PEEPHOLE1(ID, I1) do { PRINT_PEEPHOLE(ID, 0, I1); } while (0)
  55 #define PRINT_PEEPHOLE2(ID, I1, I2) \
  56   do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); } while (0)
  57 #define PRINT_PEEPHOLE3(ID, I1, I2, I3) \
  58   do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); \
  59        PRINT_PEEPHOLE(ID, 2, I3); } while (0)
  60
  61
  62 // isReinterpretingCast - Return true if the cast instruction specified will
  63 // cause the operand to be "reinterpreted".  A value is reinterpreted if the
  64 // cast instruction would cause the underlying bits to change.
  65 //
  66 static inline bool isReinterpretingCast(const CastInst *CI) {
  67   return !losslessCastableTypes(CI->getOperand(0)->getType(), CI->getType());
  68 }
  69
  70
  71 // getPointedToStruct - If the argument is a pointer type, and the pointed to
  72 // value is a struct type, return the struct type, else return null.
  73 //
  74 static const StructType *getPointedToStruct(const Type *Ty) {
  75   const PointerType *PT = dyn_cast<PointerType>(Ty);
  76   return PT ? dyn_cast<StructType>(PT->getValueType()) : 0;
  77 }
  78
  79
  80 // getStructOffsetType - Return a vector of offsets that are to be used to index
  81 // into the specified struct type to get as close as possible to index as we
  82 // can.  Note that it is possible that we cannot get exactly to Offset, in which
  83 // case we update offset to be the offset we actually obtained.  The resultant
  84 // leaf type is returned.
  85 //
  86 static const Type *getStructOffsetType(const Type *Ty, unsigned &Offset,
  87                                        vector<ConstPoolVal*> &Offsets) {
  88   if (!isa<StructType>(Ty)) {
  89     Offset = 0;   // Return the offset that we were able to acheive
  90     return Ty;    // Return the leaf type
  91   }
  92
  93   assert(Offset < TD.getTypeSize(Ty) && "Offset not in struct!");
  94   const StructType *STy = cast<StructType>(Ty);
  95   const StructLayout *SL = TD.getStructLayout(STy);
  96
  97   // This loop terminates always on a 0 <= i < MemberOffsets.size()
  98   unsigned i;
  99   for (i = 0; i < SL->MemberOffsets.size()-1; ++i)
 100     if (Offset >= SL->MemberOffsets[i] && Offset <  SL->MemberOffsets[i+1])
 101       break;
 102
 103   assert(Offset >= SL->MemberOffsets[i] &&
 104          (i == SL->MemberOffsets.size()-1 || Offset <  SL->MemberOffsets[i+1]));
 105
 106   // Make sure to save the current index...
 107   Offsets.push_back(ConstPoolUInt::get(Type::UByteTy, i));
 108
 109   unsigned SubOffs = Offset - SL->MemberOffsets[i];
 110   const Type *LeafTy = getStructOffsetType(STy->getElementTypes()[i], SubOffs,
 111                                            Offsets);
 112   Offset = SL->MemberOffsets[i] + SubOffs;
 113   return LeafTy;
 114 }
 115
 116
 117
 118
 119
 120 // DoInsertArrayCast - If the argument value has a pointer type, and if the
 121 // argument value is used as an array, insert a cast before the specified
 122 // basic block iterator that casts the value to an array pointer.  Return the
 123 // new cast instruction (in the CastResult var), or null if no cast is inserted.
 124 //
 125 static bool DoInsertArrayCast(Method *CurMeth, Value *V, BasicBlock *BB,
 126                               BasicBlock::iterator &InsertBefore,
 127                               CastInst *&CastResult) {
 128   const PointerType *ThePtrType = dyn_cast<PointerType>(V->getType());
 129   if (!ThePtrType) return false;
 130   bool InsertCast = false;
 131
 132   for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I) {
 133     Instruction *Inst = cast<Instruction>(*I);
 134     switch (Inst->getOpcode()) {
 135     default: break;                  // Not an interesting use...
 136     case Instruction::Add:           // It's being used as an array index!
 137   //case Instruction::Sub:
 138       InsertCast = true;
 139       break;
 140     case Instruction::Cast:          // There is already a cast instruction!
 141       if (const PointerType *PT = dyn_cast<const PointerType>(Inst->getType()))
 142         if (const ArrayType *AT = dyn_cast<const ArrayType>(PT->getValueType()))
 143           if (AT->getElementType() == ThePtrType->getValueType()) {
 144             // Cast already exists! Return the existing one!
 145             CastResult = cast<CastInst>(Inst);
 146             return false;       // No changes made to program though...
 147           }
 148       break;
 149     }
 150   }
 151
 152   if (!InsertCast) return false;  // There is no reason to insert a cast!
 153
 154   // Insert a cast!
 155   const Type *ElTy = ThePtrType->getValueType();
 156   const PointerType *DestTy = PointerType::get(ArrayType::get(ElTy));
 157
 158   CastResult = new CastInst(V, DestTy);
 159   BB->getInstList().insert(InsertBefore, CastResult);
 160   //cerr << "Inserted cast: " << CastResult;
 161   return true;            // Made a change!
 162 }
 163
 164
 165 // DoInsertArrayCasts - Loop over all "incoming" values in the specified method,
 166 // inserting a cast for pointer values that are used as arrays. For our
 167 // purposes, an incoming value is considered to be either a value that is
 168 // either a method parameter, a value created by alloca or malloc, or a value
 169 // returned from a function call.  All casts are kept attached to their original
 170 // values through the PtrCasts map.
 171 //
 172 static bool DoInsertArrayCasts(Method *M, map<Value*, CastInst*> &PtrCasts) {
 173   assert(!M->isExternal() && "Can't handle external methods!");
 174
 175   // Insert casts for all arguments to the function...
 176   bool Changed = false;
 177   BasicBlock *CurBB = M->front();
 178   BasicBlock::iterator It = CurBB->begin();
 179   for (Method::ArgumentListType::iterator AI = M->getArgumentList().begin(),
 180          AE = M->getArgumentList().end(); AI != AE; ++AI) {
 181     CastInst *TheCast = 0;
 182     if (DoInsertArrayCast(M, *AI, CurBB, It, TheCast)) {
 183       It = CurBB->begin();      // We might have just invalidated the iterator!
 184       Changed = true;           // Yes we made a change
 185       ++It;                     // Insert next cast AFTER this one...
 186     }
 187
 188     if (TheCast)                // Is there a cast associated with this value?
 189       PtrCasts[*AI] = TheCast;  // Yes, add it to the map...
 190   }
 191
 192   // TODO: insert casts for alloca, malloc, and function call results.  Also,
 193   // look for pointers that already have casts, to add to the map.
 194
 195   return Changed;
 196 }
 197
 198
 199
 200
 201 // DoElminatePointerArithmetic - Loop over each incoming pointer variable,
 202 // replacing indexing arithmetic with getelementptr calls.
 203 //
 204 static bool DoEliminatePointerArithmetic(const pair<Value*, CastInst*> &Val) {
 205   Value    *V  = Val.first;   // The original pointer
 206   CastInst *CV = Val.second;  // The array casted version of the pointer...
 207
 208   for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I) {
 209     Instruction *Inst = cast<Instruction>(*I);
 210     if (Inst->getOpcode() != Instruction::Add)
 211       continue;   // We only care about add instructions
 212
 213     BinaryOperator *Add = cast<BinaryOperator>(Inst);
 214
 215     // Make sure the array is the first operand of the add expression...
 216     if (Add->getOperand(0) != V)
 217       Add->swapOperands();
 218
 219     // Get the amount added to the pointer value...
 220     Value *AddAmount = Add->getOperand(1);
 221
 222
 223   }
 224   return false;
 225 }
 226
 227
 228 // Peephole Malloc instructions: we take a look at the use chain of the
 229 // malloc instruction, and try to find out if the following conditions hold:
 230 //   1. The malloc is of the form: 'malloc [sbyte], uint <constant>'
 231 //   2. The only users of the malloc are cast & add instructions
 232 //   3. Of the cast instructions, there is only one destination pointer type
 233 //      [RTy] where the size of the pointed to object is equal to the number
 234 //      of bytes allocated.
 235 //
 236 // If these conditions hold, we convert the malloc to allocate an [RTy]
 237 // element.  This should be extended in the future to handle arrays. TODO
 238 //
 239 static bool PeepholeMallocInst(BasicBlock *BB, BasicBlock::iterator &BI) {
 240   MallocInst *MI = cast<MallocInst>(*BI);
 241   if (!MI->isArrayAllocation()) return false;    // No array allocation?
 242
 243   ConstPoolUInt *Amt = dyn_cast<ConstPoolUInt>(MI->getArraySize());
 244   if (Amt == 0 || MI->getAllocatedType() != ArrayType::get(Type::SByteTy))
 245     return false;
 246
 247   // Get the number of bytes allocated...
 248   unsigned Size = Amt->getValue();
 249   const Type *ResultTy = 0;
 250
 251   // Loop over all of the uses of the malloc instruction, inspecting casts.
 252   for (Value::use_iterator I = MI->use_begin(), E = MI->use_end();
 253        I != E; ++I) {
 254     if (!isa<CastInst>(*I) && !isa<BinaryOperator>(*I)) {
 255       //cerr << "\tnon" << *I;
 256       return false;  // A non cast user?
 257     }
 258     if (CastInst *CI = dyn_cast<CastInst>(*I)) {
 259         //cerr << "\t" << CI;
 260
 261       // We only work on casts to pointer types for sure, be conservative
 262       if (!isa<PointerType>(CI->getType())) {
 263         cerr << "Found cast of malloc value to non pointer type:\n" << CI;
 264         return false;
 265       }
 266
 267       const Type *DestTy = cast<PointerType>(CI->getType())->getValueType();
 268       if (TD.getTypeSize(DestTy) == Size && DestTy != ResultTy) {
 269         // Does the size of the allocated type match the number of bytes
 270         // allocated?
 271         //
 272         if (ResultTy == 0) {
 273           ResultTy = DestTy;   // Keep note of this for future uses...
 274         } else {
 275           // It's overdefined!  We don't know which type to convert to!
 276           return false;
 277         }
 278       }
 279     }
 280   }
 281
 282   // If we get this far, we have either found, or not, a type that is cast to
 283   // that is of the same size as the malloc instruction.
 284   if (!ResultTy) return false;
 285
 286   PRINT_PEEPHOLE1("mall-refine:in ", MI);
 287   ReplaceInstWithInst(BB->getInstList(), BI,
 288                       MI = new MallocInst(PointerType::get(ResultTy)));
 289   PRINT_PEEPHOLE1("mall-refine:out", MI);
 290   return true;
 291 }
 292
 293
 294 // Peephole optimize the following instructions:
 295 //   %t1 = cast int (uint) * %reg111 to uint (...) *
 296 //   %t2 = call uint (...) * %cast111( uint %key )
 297 //
 298 // Into: %t3 = call int (uint) * %reg111( uint %key )
 299 //       %t2 = cast int %t3 to uint
 300 //
 301 static bool PeepholeCallInst(BasicBlock *BB, BasicBlock::iterator &BI) {
 302   CallInst *CI = cast<CallInst>(*BI);
 303   return false;
 304 }
 305
 306
 307 static bool PeepholeOptimize(BasicBlock *BB, BasicBlock::iterator &BI) {
 308   Instruction *I = *BI;
 309
 310   if (CastInst *CI = dyn_cast<CastInst>(I)) {
 311     Value       *Src    = CI->getOperand(0);
 312     Instruction *SrcI   = dyn_cast<Instruction>(Src); // Nonnull if instr source
 313     const Type  *DestTy = CI->getType();
 314
 315     // Peephole optimize the following instruction:
 316     // %V2 = cast <ty> %V to <ty>
 317     //
 318     // Into: <nothing>
 319     //
 320     if (DestTy == Src->getType()) {   // Check for a cast to same type as src!!
 321       PRINT_PEEPHOLE1("cast-of-self-ty", CI);
 322       CI->replaceAllUsesWith(Src);
 323       if (!Src->hasName() && CI->hasName()) {
 324         string Name = CI->getName();
 325         CI->setName("");
 326         Src->setName(Name, BB->getParent()->getSymbolTable());
 327       }
 328       return true;
 329     }
 330
 331     // Peephole optimize the following instructions:
 332     // %tmp = cast <ty> %V to <ty2>
 333     // %V  = cast <ty2> %tmp to <ty3>     ; Where ty & ty2 are same size
 334     //
 335     // Into: cast <ty> %V to <ty3>
 336     //
 337     if (SrcI)
 338       if (CastInst *CSrc = dyn_cast<CastInst>(SrcI))
 339         if (isReinterpretingCast(CI) + isReinterpretingCast(CSrc) < 2) {
 340           // We can only do c-c elimination if, at most, one cast does a
 341           // reinterpretation of the input data.
 342           //
 343           // If legal, make this cast refer the the original casts argument!
 344           //
 345           PRINT_PEEPHOLE2("cast-cast:in ", CI, CSrc);
 346           CI->setOperand(0, CSrc->getOperand(0));
 347           PRINT_PEEPHOLE1("cast-cast:out", CI);
 348           return true;
 349         }
 350
 351     // Check to see if it's a cast of an instruction that does not depend on the
 352     // specific type of the operands to do it's job.
 353     if (!isReinterpretingCast(CI)) {
 354       ValueTypeCache ConvertedTypes;
 355       if (RetValConvertableToType(CI, Src->getType(), ConvertedTypes)) {
 356         PRINT_PEEPHOLE2("CAST-DEST-EXPR-CONV:in ", CI, Src);
 357
 358         ValueMapCache ValueMap;
 359         ConvertUsersType(CI, Src, ValueMap);  // This will delete CI!
 360
 361         BI = BB->begin();  // Rescan basic block.  BI might be invalidated.
 362         PRINT_PEEPHOLE1("CAST-DEST-EXPR-CONV:out", I);
 363         return true;
 364       }
 365     }
 366
 367     // Check to see if we are casting from a structure pointer to a pointer to
 368     // the first element of the structure... to avoid munching other peepholes,
 369     // we only let this happen if there are no add uses of the cast.
 370     //
 371     // Peephole optimize the following instructions:
 372     // %t1 = cast {<...>} * %StructPtr to <ty> *
 373     //
 374     // Into: %t2 = getelementptr {<...>} * %StructPtr, <0, 0, 0, ...>
 375     //       %t1 = cast <eltype> * %t1 to <ty> *
 376     //
 377     if (const StructType *STy = getPointedToStruct(Src->getType()))
 378       if (const PointerType *DestPTy = dyn_cast<PointerType>(DestTy)) {
 379
 380         // Loop over uses of the cast, checking for add instructions.  If an add
 381         // exists, this is probably a part of a more complex GEP, so we don't
 382         // want to mess around with the cast.
 383         //
 384         bool HasAddUse = false;
 385         for (Value::use_iterator I = CI->use_begin(), E = CI->use_end();
 386              I != E; ++I)
 387           if (isa<Instruction>(*I) &&
 388               cast<Instruction>(*I)->getOpcode() == Instruction::Add) {
 389             HasAddUse = true; break;
 390           }
 391
 392         // If it doesn't have an add use, check to see if the dest type is
 393         // losslessly convertable to one of the types in the start of the struct
 394         // type.
 395         //
 396         if (!HasAddUse) {
 397           const Type *DestPointedTy = DestPTy->getValueType();
 398           unsigned Depth = 1;
 399           const StructType *CurSTy = STy;
 400           const Type *ElTy = 0;
 401           while (CurSTy) {
 402
 403             // Check for a zero element struct type... if we have one, bail.
 404             if (CurSTy->getElementTypes().size() == 0) break;
 405
 406             // Grab the first element of the struct type, which must lie at
 407             // offset zero in the struct.
 408             //
 409             ElTy = CurSTy->getElementTypes()[0];
 410
 411             // Did we find what we're looking for?
 412             if (losslessCastableTypes(ElTy, DestPointedTy)) break;
 413
 414             // Nope, go a level deeper.
 415             ++Depth;
 416             CurSTy = dyn_cast<StructType>(ElTy);
 417             ElTy = 0;
 418           }
 419
 420           // Did we find what we were looking for? If so, do the transformation
 421           if (ElTy) {
 422             PRINT_PEEPHOLE1("cast-for-first:in", CI);
 423
 424             // Build the index vector, full of all zeros
 425             vector<ConstPoolVal *> Indices(Depth,
 426                                            ConstPoolUInt::get(Type::UByteTy,0));
 427
 428             // Insert the new T cast instruction... stealing old T's name
 429             GetElementPtrInst *GEP = new GetElementPtrInst(Src, Indices,
 430                                                            CI->getName());
 431             CI->setName("");
 432             BI = BB->getInstList().insert(BI, GEP)+1;
 433
 434             // Make the old cast instruction reference the new GEP instead of
 435             // the old src value.
 436             //
 437             CI->setOperand(0, GEP);
 438
 439             PRINT_PEEPHOLE2("cast-for-first:out", GEP, CI);
 440             return true;
 441           }
 442         }
 443       }
 444
 445
 446   } else if (MallocInst *MI = dyn_cast<MallocInst>(I)) {
 447     if (PeepholeMallocInst(BB, BI)) return true;
 448
 449   } else if (CallInst *CI = dyn_cast<CallInst>(I)) {
 450     if (PeepholeCallInst(BB, BI)) return true;
 451
 452   } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 453     Value *Val     = SI->getOperand(0);
 454     Value *Pointer = SI->getPtrOperand();
 455
 456     // Peephole optimize the following instructions:
 457     // %t1 = getelementptr {<...>} * %StructPtr, <element indices>
 458     // store <elementty> %v, <elementty> * %t1
 459     //
 460     // Into: store <elementty> %v, {<...>} * %StructPtr, <element indices>
 461     //
 462     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Pointer)) {
 463       PRINT_PEEPHOLE2("gep-store:in", GEP, SI);
 464       ReplaceInstWithInst(BB->getInstList(), BI,
 465                           SI = new StoreInst(Val, GEP->getPtrOperand(),
 466                                              GEP->getIndices()));
 467       PRINT_PEEPHOLE1("gep-store:out", SI);
 468       return true;
 469     }
 470
 471     // Peephole optimize the following instructions:
 472     // %t = cast <T1>* %P to <T2> * ;; If T1 is losslessly convertable to T2
 473     // store <T2> %V, <T2>* %t
 474     //
 475     // Into:
 476     // %t = cast <T2> %V to <T1>
 477     // store <T1> %t2, <T1>* %P
 478     //
 479     if (CastInst *CI = dyn_cast<CastInst>(Pointer))
 480       if (Value *CastSrc = CI->getOperand(0)) // CSPT = CastSrcPointerType
 481         if (PointerType *CSPT = dyn_cast<PointerType>(CastSrc->getType()))
 482           if (losslessCastableTypes(Val->getType(), // convertable types!
 483                                     CSPT->getValueType()) &&
 484               !SI->hasIndices()) {      // No subscripts yet!
 485             PRINT_PEEPHOLE3("st-src-cast:in ", Pointer, Val, SI);
 486
 487             // Insert the new T cast instruction... stealing old T's name
 488             CastInst *NCI = new CastInst(Val, CSPT->getValueType(),
 489                                          CI->getName());
 490             CI->setName("");
 491             BI = BB->getInstList().insert(BI, NCI)+1;
 492
 493             // Replace the old store with a new one!
 494             ReplaceInstWithInst(BB->getInstList(), BI,
 495                                 SI = new StoreInst(NCI, CastSrc));
 496             PRINT_PEEPHOLE3("st-src-cast:out", NCI, CastSrc, SI);
 497             return true;
 498           }
 499
 500
 501   } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
 502     Value *Pointer = LI->getPtrOperand();
 503
 504     // Peephole optimize the following instructions:
 505     // %t1 = getelementptr {<...>} * %StructPtr, <element indices>
 506     // %V  = load <elementty> * %t1
 507     //
 508     // Into: load {<...>} * %StructPtr, <element indices>
 509     //
 510     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Pointer)) {
 511       PRINT_PEEPHOLE2("gep-load:in", GEP, LI);
 512       ReplaceInstWithInst(BB->getInstList(), BI,
 513                           LI = new LoadInst(GEP->getPtrOperand(),
 514                                             GEP->getIndices()));
 515       PRINT_PEEPHOLE1("gep-load:out", LI);
 516       return true;
 517     }
 518   } else if (I->getOpcode() == Instruction::Add &&
 519              isa<CastInst>(I->getOperand(1))) {
 520
 521     // Peephole optimize the following instructions:
 522     // %t1 = cast ulong <const int> to {<...>} *
 523     // %t2 = add {<...>} * %SP, %t1              ;; Constant must be 2nd operand
 524     //
 525     //    or
 526     // %t1 = cast {<...>}* %SP to int*
 527     // %t5 = cast ulong <const int> to int*
 528     // %t2 = add int* %t1, %t5                   ;; int is same size as field
 529     //
 530     // Into: %t3 = getelementptr {<...>} * %SP, <element indices>
 531     //       %t2 = cast <eltype> * %t3 to {<...>}*
 532     //
 533     Value            *AddOp1  = I->getOperand(0);
 534     CastInst         *AddOp2  = cast<CastInst>(I->getOperand(1));
 535     ConstPoolUInt    *OffsetV = dyn_cast<ConstPoolUInt>(AddOp2->getOperand(0));
 536     unsigned          Offset  = OffsetV ? OffsetV->getValue() : 0;
 537     Value            *SrcPtr;  // Of type pointer to struct...
 538     const StructType *StructTy;
 539
 540     if ((StructTy = getPointedToStruct(AddOp1->getType()))) {
 541       SrcPtr = AddOp1;                      // Handle the first case...
 542     } else if (CastInst *AddOp1c = dyn_cast<CastInst>(AddOp1)) {
 543       SrcPtr = AddOp1c->getOperand(0);      // Handle the second case...
 544       StructTy = getPointedToStruct(SrcPtr->getType());
 545     }
 546
 547     // Only proceed if we have detected all of our conditions successfully...
 548     if (Offset && StructTy && SrcPtr && Offset < TD.getTypeSize(StructTy)) {
 549       const StructLayout *SL = TD.getStructLayout(StructTy);
 550       vector<ConstPoolVal*> Offsets;
 551       unsigned ActualOffset = Offset;
 552       const Type *ElTy = getStructOffsetType(StructTy, ActualOffset, Offsets);
 553
 554       if (getPointedToStruct(AddOp1->getType())) {  // case 1
 555         PRINT_PEEPHOLE2("add-to-gep1:in", AddOp2, I);
 556       } else {
 557         PRINT_PEEPHOLE3("add-to-gep2:in", AddOp1, AddOp2, I);
 558       }
 559
 560       GetElementPtrInst *GEP = new GetElementPtrInst(SrcPtr, Offsets);
 561       BI = BB->getInstList().insert(BI, GEP)+1;
 562
 563       assert(Offset-ActualOffset == 0  &&
 564              "GEP to middle of element not implemented yet!");
 565
 566       ReplaceInstWithInst(BB->getInstList(), BI,
 567                           I = new CastInst(GEP, I->getType()));
 568       PRINT_PEEPHOLE2("add-to-gep:out", GEP, I);
 569       return true;
 570     }
 571   }
 572
 573   return false;
 574 }
 575
 576
 577
 578
 579 static bool DoRaisePass(Method *M) {
 580   bool Changed = false;
 581   for (Method::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI) {
 582     BasicBlock *BB = *MI;
 583     BasicBlock::InstListType &BIL = BB->getInstList();
 584
 585     for (BasicBlock::iterator BI = BB->begin(); BI != BB->end();) {
 586       if (opt::DeadCodeElimination::dceInstruction(BIL, BI) ||
 587           PeepholeOptimize(BB, BI))
 588         Changed = true;
 589       else
 590         ++BI;
 591     }
 592   }
 593   return Changed;
 594 }
 595
 596
 597 // RaisePointerReferences::doit - Raise a method representation to a higher
 598 // level.
 599 //
 600 bool RaisePointerReferences::doit(Method *M) {
 601   if (M->isExternal()) return false;
 602   bool Changed = false;
 603
 604 #ifdef DEBUG_PEEPHOLE_INSTS
 605   cerr << "\n\n\nStarting to work on Method '" << M->getName() << "'\n";
 606 #endif
 607
 608   while (DoRaisePass(M)) Changed = true;
 609
 610   // PtrCasts - Keep a mapping between the pointer values (the key of the
 611   // map), and the cast to array pointer (the value) in this map.  This is
 612   // used when converting pointer math into array addressing.
 613   //
 614   map<Value*, CastInst*> PtrCasts;
 615
 616   // Insert casts for all incoming pointer values.  Keep track of those casts
 617   // and the identified incoming values in the PtrCasts map.
 618   //
 619   Changed |= DoInsertArrayCasts(M, PtrCasts);
 620
 621   // Loop over each incoming pointer variable, replacing indexing arithmetic
 622   // with getelementptr calls.
 623   //
 624   Changed |= reduce_apply_bool(PtrCasts.begin(), PtrCasts.end(),
 625                                ptr_fun(DoEliminatePointerArithmetic));
 626
 627   return Changed;
 628 }