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::Shl:
 224     return ExpressionConvertableToType(I->getOperand(0), Ty);
 225   case Instruction::Shr:
 226     if (Ty->isSigned() != V->getType()->isSigned()) return false;
 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 // DoInsertArrayCast - If the argument value has a pointer type, and if the
 373 // argument value is used as an array, insert a cast before the specified
 374 // basic block iterator that casts the value to an array pointer.  Return the
 375 // new cast instruction (in the CastResult var), or null if no cast is inserted.
 376 //
 377 static bool DoInsertArrayCast(Method *CurMeth, Value *V, BasicBlock *BB,
 378                               BasicBlock::iterator &InsertBefore,
 379                               CastInst *&CastResult) {
 380   const PointerType *ThePtrType = dyn_cast<PointerType>(V->getType());
 381   if (!ThePtrType) return false;
 382   bool InsertCast = false;
 383
 384   for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I) {
 385     Instruction *Inst = cast<Instruction>(*I);
 386     switch (Inst->getOpcode()) {
 387     default: break;                  // Not an interesting use...
 388     case Instruction::Add:           // It's being used as an array index!
 389   //case Instruction::Sub:
 390       InsertCast = true;
 391       break;
 392     case Instruction::Cast:          // There is already a cast instruction!
 393       if (const PointerType *PT = dyn_cast<const PointerType>(Inst->getType()))
 394         if (const ArrayType *AT = dyn_cast<const ArrayType>(PT->getValueType()))
 395           if (AT->getElementType() == ThePtrType->getValueType()) {
 396             // Cast already exists! Return the existing one!
 397             CastResult = cast<CastInst>(Inst);
 398             return false;       // No changes made to program though...
 399           }
 400       break;
 401     }
 402   }
 403
 404   if (!InsertCast) return false;  // There is no reason to insert a cast!
 405
 406   // Insert a cast!
 407   const Type *ElTy = ThePtrType->getValueType();
 408   const PointerType *DestTy = PointerType::get(ArrayType::get(ElTy));
 409
 410   CastResult = new CastInst(V, DestTy);
 411   BB->getInstList().insert(InsertBefore, CastResult);
 412   //cerr << "Inserted cast: " << CastResult;
 413   return true;            // Made a change!
 414 }
 415
 416
 417 // DoInsertArrayCasts - Loop over all "incoming" values in the specified method,
 418 // inserting a cast for pointer values that are used as arrays. For our
 419 // purposes, an incoming value is considered to be either a value that is
 420 // either a method parameter, a value created by alloca or malloc, or a value
 421 // returned from a function call.  All casts are kept attached to their original
 422 // values through the PtrCasts map.
 423 //
 424 static bool DoInsertArrayCasts(Method *M, map<Value*, CastInst*> &PtrCasts) {
 425   assert(!M->isExternal() && "Can't handle external methods!");
 426
 427   // Insert casts for all arguments to the function...
 428   bool Changed = false;
 429   BasicBlock *CurBB = M->front();
 430   BasicBlock::iterator It = CurBB->begin();
 431   for (Method::ArgumentListType::iterator AI = M->getArgumentList().begin(),
 432          AE = M->getArgumentList().end(); AI != AE; ++AI) {
 433     CastInst *TheCast = 0;
 434     if (DoInsertArrayCast(M, *AI, CurBB, It, TheCast)) {
 435       It = CurBB->begin();      // We might have just invalidated the iterator!
 436       Changed = true;           // Yes we made a change
 437       ++It;                     // Insert next cast AFTER this one...
 438     }
 439
 440     if (TheCast)                // Is there a cast associated with this value?
 441       PtrCasts[*AI] = TheCast;  // Yes, add it to the map...
 442   }
 443
 444   // TODO: insert casts for alloca, malloc, and function call results.  Also,
 445   // look for pointers that already have casts, to add to the map.
 446
 447   return Changed;
 448 }
 449
 450
 451
 452
 453 // DoElminatePointerArithmetic - Loop over each incoming pointer variable,
 454 // replacing indexing arithmetic with getelementptr calls.
 455 //
 456 static bool DoEliminatePointerArithmetic(const pair<Value*, CastInst*> &Val) {
 457   Value    *V  = Val.first;   // The original pointer
 458   CastInst *CV = Val.second;  // The array casted version of the pointer...
 459
 460   for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I) {
 461     Instruction *Inst = cast<Instruction>(*I);
 462     if (Inst->getOpcode() != Instruction::Add)
 463       continue;   // We only care about add instructions
 464
 465     BinaryOperator *Add = cast<BinaryOperator>(Inst);
 466
 467     // Make sure the array is the first operand of the add expression...
 468     if (Add->getOperand(0) != V)
 469       Add->swapOperands();
 470
 471     // Get the amount added to the pointer value...
 472     Value *AddAmount = Add->getOperand(1);
 473
 474
 475   }
 476   return false;
 477 }
 478
 479
 480 // Peephole Malloc instructions: we take a look at the use chain of the
 481 // malloc instruction, and try to find out if the following conditions hold:
 482 //   1. The malloc is of the form: 'malloc [sbyte], uint <constant>'
 483 //   2. The only users of the malloc are cast instructions
 484 //   3. Of the cast instructions, there is only one destination pointer type
 485 //      [RTy] where the size of the pointed to object is equal to the number
 486 //      of bytes allocated.
 487 //
 488 // If these conditions hold, we convert the malloc to allocate an [RTy]
 489 // element.  This should be extended in the future to handle arrays. TODO
 490 //
 491 static bool PeepholeMallocInst(BasicBlock *BB, BasicBlock::iterator &BI) {
 492   MallocInst *MI = cast<MallocInst>(*BI);
 493   if (!MI->isArrayAllocation()) return false;    // No array allocation?
 494
 495   ConstPoolUInt *Amt = dyn_cast<ConstPoolUInt>(MI->getArraySize());
 496   if (Amt == 0 || MI->getAllocatedType() != ArrayType::get(Type::SByteTy))
 497     return false;
 498
 499   // Get the number of bytes allocated...
 500   unsigned Size = Amt->getValue();
 501   const Type *ResultTy = 0;
 502
 503   // Loop over all of the uses of the malloc instruction, inspecting casts.
 504   for (Value::use_iterator I = MI->use_begin(), E = MI->use_end();
 505        I != E; ++I) {
 506     if (!isa<CastInst>(*I)) {
 507       //cerr << "\tnon" << *I;
 508       return false;  // A non cast user?
 509     }
 510     CastInst *CI = cast<CastInst>(*I);
 511     //cerr << "\t" << CI;
 512
 513     // We only work on casts to pointer types for sure, be conservative
 514     if (!isa<PointerType>(CI->getType())) {
 515       cerr << "Found cast of malloc value to non pointer type:\n" << CI;
 516       return false;
 517     }
 518
 519     const Type *DestTy = cast<PointerType>(CI->getType())->getValueType();
 520     if (TD.getTypeSize(DestTy) == Size && DestTy != ResultTy) {
 521       // Does the size of the allocated type match the number of bytes
 522       // allocated?
 523       //
 524       if (ResultTy == 0) {
 525         ResultTy = DestTy;   // Keep note of this for future uses...
 526       } else {
 527         // It's overdefined!  We don't know which type to convert to!
 528         return false;
 529       }
 530     }
 531   }
 532
 533   // If we get this far, we have either found, or not, a type that is cast to
 534   // that is of the same size as the malloc instruction.
 535   if (!ResultTy) return false;
 536
 537   PRINT_PEEPHOLE1("mall-refine:in ", MI);
 538   ReplaceInstWithInst(BB->getInstList(), BI,
 539                       MI = new MallocInst(PointerType::get(ResultTy)));
 540   PRINT_PEEPHOLE1("mall-refine:out", MI);
 541   return true;
 542 }
 543
 544
 545 // Peephole optimize the following instructions:
 546 //   %t1 = cast int (uint) * %reg111 to uint (...) *
 547 //   %t2 = call uint (...) * %cast111( uint %key )
 548 //
 549 // Into: %t3 = call int (uint) * %reg111( uint %key )
 550 //       %t2 = cast int %t3 to uint
 551 //
 552 static bool PeepholeCallInst(BasicBlock *BB, BasicBlock::iterator &BI) {
 553   CallInst *CI = cast<CallInst>(*BI);
 554   return false;
 555 }
 556
 557
 558 static bool PeepholeOptimize(BasicBlock *BB, BasicBlock::iterator &BI) {
 559   Instruction *I = *BI;
 560
 561   if (CastInst *CI = dyn_cast<CastInst>(I)) {
 562     Value       *Src    = CI->getOperand(0);
 563     Instruction *SrcI   = dyn_cast<Instruction>(Src); // Nonnull if instr source
 564     const Type  *DestTy = CI->getType();
 565
 566     // Peephole optimize the following instruction:
 567     // %V2 = cast <ty> %V to <ty>
 568     //
 569     // Into: <nothing>
 570     //
 571     if (DestTy == Src->getType()) {   // Check for a cast to same type as src!!
 572       PRINT_PEEPHOLE1("cast-of-self-ty", CI);
 573       CI->replaceAllUsesWith(Src);
 574       if (!Src->hasName() && CI->hasName()) {
 575         string Name = CI->getName();
 576         CI->setName(""); Src->setName(Name,
 577                                       BB->getParent()->getSymbolTable());
 578       }
 579       return true;
 580     }
 581
 582     // Peephole optimize the following instructions:
 583     // %tmp = cast <ty> %V to <ty2>
 584     // %V  = cast <ty2> %tmp to <ty3>     ; Where ty & ty2 are same size
 585     //
 586     // Into: cast <ty> %V to <ty3>
 587     //
 588     if (SrcI)
 589       if (CastInst *CSrc = dyn_cast<CastInst>(SrcI))
 590         if (isReinterpretingCast(CI) + isReinterpretingCast(CSrc) < 2) {
 591           // We can only do c-c elimination if, at most, one cast does a
 592           // reinterpretation of the input data.
 593           //
 594           // If legal, make this cast refer the the original casts argument!
 595           //
 596           PRINT_PEEPHOLE2("cast-cast:in ", CI, CSrc);
 597           CI->setOperand(0, CSrc->getOperand(0));
 598           PRINT_PEEPHOLE1("cast-cast:out", CI);
 599           return true;
 600         }
 601
 602     // Check to see if it's a cast of an instruction that does not depend on the
 603     // specific type of the operands to do it's job.
 604     if (!isReinterpretingCast(CI) &&
 605         ExpressionConvertableToType(Src, DestTy)) {
 606       PRINT_PEEPHOLE2("EXPR-CONV:in ", CI, Src);
 607       CI->setOperand(0, ConvertExpressionToType(Src, DestTy));
 608       BI = BB->begin();  // Rescan basic block.  BI might be invalidated.
 609       PRINT_PEEPHOLE2("EXPR-CONV:out", CI, CI->getOperand(0));
 610       return true;
 611     }
 612
 613     // Check to see if we are casting from a structure pointer to a pointer to
 614     // the first element of the structure... to avoid munching other peepholes,
 615     // we only let this happen if there are no add uses of the cast.
 616     //
 617     // Peephole optimize the following instructions:
 618     // %t1 = cast {<...>} * %StructPtr to <ty> *
 619     //
 620     // Into: %t2 = getelementptr {<...>} * %StructPtr, <0, 0, 0, ...>
 621     //       %t1 = cast <eltype> * %t1 to <ty> *
 622     //
 623     if (const StructType *STy = getPointedToStruct(Src->getType()))
 624       if (const PointerType *DestPTy = dyn_cast<PointerType>(DestTy)) {
 625
 626         // Loop over uses of the cast, checking for add instructions.  If an add
 627         // exists, this is probably a part of a more complex GEP, so we don't
 628         // want to mess around with the cast.
 629         //
 630         bool HasAddUse = false;
 631         for (Value::use_iterator I = CI->use_begin(), E = CI->use_end();
 632              I != E; ++I)
 633           if (isa<Instruction>(*I) &&
 634               cast<Instruction>(*I)->getOpcode() == Instruction::Add) {
 635             HasAddUse = true; break;
 636           }
 637
 638         // If it doesn't have an add use, check to see if the dest type is
 639         // losslessly convertable to one of the types in the start of the struct
 640         // type.
 641         //
 642         if (!HasAddUse) {
 643           const Type *DestPointedTy = DestPTy->getValueType();
 644           unsigned Depth = 1;
 645           const StructType *CurSTy = STy;
 646           const Type *ElTy = 0;
 647           while (CurSTy) {
 648
 649             // Check for a zero element struct type... if we have one, bail.
 650             if (CurSTy->getElementTypes().size() == 0) break;
 651
 652             // Grab the first element of the struct type, which must lie at
 653             // offset zero in the struct.
 654             //
 655             ElTy = CurSTy->getElementTypes()[0];
 656
 657             // Did we find what we're looking for?
 658             if (losslessCastableTypes(ElTy, DestPointedTy)) break;
 659
 660             // Nope, go a level deeper.
 661             ++Depth;
 662             CurSTy = dyn_cast<StructType>(ElTy);
 663             ElTy = 0;
 664           }
 665
 666           // Did we find what we were looking for? If so, do the transformation
 667           if (ElTy) {
 668             PRINT_PEEPHOLE1("cast-for-first:in", CI);
 669
 670             // Build the index vector, full of all zeros
 671             vector<ConstPoolVal *> Indices(Depth,
 672                                            ConstPoolUInt::get(Type::UByteTy,0));
 673
 674             // Insert the new T cast instruction... stealing old T's name
 675             GetElementPtrInst *GEP = new GetElementPtrInst(Src, Indices,
 676                                                            CI->getName());
 677             CI->setName("");
 678             BI = BB->getInstList().insert(BI, GEP)+1;
 679
 680             // Make the old cast instruction reference the new GEP instead of
 681             // the old src value.
 682             //
 683             CI->setOperand(0, GEP);
 684
 685             PRINT_PEEPHOLE2("cast-for-first:out", GEP, CI);
 686             return true;
 687           }
 688         }
 689       }
 690
 691
 692   } else if (MallocInst *MI = dyn_cast<MallocInst>(I)) {
 693     if (PeepholeMallocInst(BB, BI)) return true;
 694
 695   } else if (CallInst *CI = dyn_cast<CallInst>(I)) {
 696     if (PeepholeCallInst(BB, BI)) return true;
 697
 698   } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 699     Value *Val     = SI->getOperand(0);
 700     Value *Pointer = SI->getPtrOperand();
 701
 702     // Peephole optimize the following instructions:
 703     // %t1 = getelementptr {<...>} * %StructPtr, <element indices>
 704     // store <elementty> %v, <elementty> * %t1
 705     //
 706     // Into: store <elementty> %v, {<...>} * %StructPtr, <element indices>
 707     //
 708     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Pointer)) {
 709       PRINT_PEEPHOLE2("gep-store:in", GEP, SI);
 710       ReplaceInstWithInst(BB->getInstList(), BI,
 711                           SI = new StoreInst(Val, GEP->getPtrOperand(),
 712                                              GEP->getIndices()));
 713       PRINT_PEEPHOLE1("gep-store:out", SI);
 714       return true;
 715     }
 716
 717     // Peephole optimize the following instructions:
 718     // %t = cast <T1>* %P to <T2> * ;; If T1 is losslessly convertable to T2
 719     // store <T2> %V, <T2>* %t
 720     //
 721     // Into:
 722     // %t = cast <T2> %V to <T1>
 723     // store <T1> %t2, <T1>* %P
 724     //
 725     if (CastInst *CI = dyn_cast<CastInst>(Pointer))
 726       if (Value *CastSrc = CI->getOperand(0)) // CSPT = CastSrcPointerType
 727         if (PointerType *CSPT = dyn_cast<PointerType>(CastSrc->getType()))
 728           if (losslessCastableTypes(Val->getType(), // convertable types!
 729                                     CSPT->getValueType()) &&
 730               !SI->hasIndices()) {      // No subscripts yet!
 731             PRINT_PEEPHOLE3("st-src-cast:in ", Pointer, Val, SI);
 732
 733             // Insert the new T cast instruction... stealing old T's name
 734             CastInst *NCI = new CastInst(Val, CSPT->getValueType(),
 735                                          CI->getName());
 736             CI->setName("");
 737             BI = BB->getInstList().insert(BI, NCI)+1;
 738
 739             // Replace the old store with a new one!
 740             ReplaceInstWithInst(BB->getInstList(), BI,
 741                                 SI = new StoreInst(NCI, CastSrc));
 742             PRINT_PEEPHOLE3("st-src-cast:out", NCI, CastSrc, SI);
 743             return true;
 744           }
 745
 746
 747   } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
 748     Value *Pointer = LI->getPtrOperand();
 749
 750     // Peephole optimize the following instructions:
 751     // %t1 = getelementptr {<...>} * %StructPtr, <element indices>
 752     // %V  = load <elementty> * %t1
 753     //
 754     // Into: load {<...>} * %StructPtr, <element indices>
 755     //
 756     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Pointer)) {
 757       PRINT_PEEPHOLE2("gep-load:in", GEP, LI);
 758       ReplaceInstWithInst(BB->getInstList(), BI,
 759                           LI = new LoadInst(GEP->getPtrOperand(),
 760                                             GEP->getIndices()));
 761       PRINT_PEEPHOLE1("gep-load:out", LI);
 762       return true;
 763     }
 764   } else if (I->getOpcode() == Instruction::Add &&
 765              isa<CastInst>(I->getOperand(1))) {
 766
 767     // Peephole optimize the following instructions:
 768     // %t1 = cast ulong <const int> to {<...>} *
 769     // %t2 = add {<...>} * %SP, %t1              ;; Constant must be 2nd operand
 770     //
 771     //    or
 772     // %t1 = cast {<...>}* %SP to int*
 773     // %t5 = cast ulong <const int> to int*
 774     // %t2 = add int* %t1, %t5                   ;; int is same size as field
 775     //
 776     // Into: %t3 = getelementptr {<...>} * %SP, <element indices>
 777     //       %t2 = cast <eltype> * %t3 to {<...>}*
 778     //
 779     Value            *AddOp1  = I->getOperand(0);
 780     CastInst         *AddOp2  = cast<CastInst>(I->getOperand(1));
 781     ConstPoolUInt    *OffsetV = dyn_cast<ConstPoolUInt>(AddOp2->getOperand(0));
 782     unsigned          Offset  = OffsetV ? OffsetV->getValue() : 0;
 783     Value            *SrcPtr;  // Of type pointer to struct...
 784     const StructType *StructTy;
 785
 786     if ((StructTy = getPointedToStruct(AddOp1->getType()))) {
 787       SrcPtr = AddOp1;                      // Handle the first case...
 788     } else if (CastInst *AddOp1c = dyn_cast<CastInst>(AddOp1)) {
 789       SrcPtr = AddOp1c->getOperand(0);      // Handle the second case...
 790       StructTy = getPointedToStruct(SrcPtr->getType());
 791     }
 792
 793     // Only proceed if we have detected all of our conditions successfully...
 794     if (Offset && StructTy && SrcPtr && Offset < TD.getTypeSize(StructTy)) {
 795       const StructLayout *SL = TD.getStructLayout(StructTy);
 796       vector<ConstPoolVal*> Offsets;
 797       unsigned ActualOffset = Offset;
 798       const Type *ElTy = getStructOffsetType(StructTy, ActualOffset, Offsets);
 799
 800       if (getPointedToStruct(AddOp1->getType())) {  // case 1
 801         PRINT_PEEPHOLE2("add-to-gep1:in", AddOp2, I);
 802       } else {
 803         PRINT_PEEPHOLE3("add-to-gep2:in", AddOp1, AddOp2, I);
 804       }
 805
 806       GetElementPtrInst *GEP = new GetElementPtrInst(SrcPtr, Offsets);
 807       BI = BB->getInstList().insert(BI, GEP)+1;
 808
 809       assert(Offset-ActualOffset == 0  &&
 810              "GEP to middle of element not implemented yet!");
 811
 812       ReplaceInstWithInst(BB->getInstList(), BI,
 813                           I = new CastInst(GEP, I->getType()));
 814       PRINT_PEEPHOLE2("add-to-gep:out", GEP, I);
 815       return true;
 816     }
 817   }
 818
 819   return false;
 820 }
 821
 822
 823
 824
 825 static bool DoRaisePass(Method *M) {
 826   bool Changed = false;
 827   for (Method::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI) {
 828     BasicBlock *BB = *MI;
 829     BasicBlock::InstListType &BIL = BB->getInstList();
 830
 831     for (BasicBlock::iterator BI = BB->begin(); BI != BB->end();) {
 832       if (opt::DeadCodeElimination::dceInstruction(BIL, BI) ||
 833           PeepholeOptimize(BB, BI))
 834         Changed = true;
 835       else
 836         ++BI;
 837     }
 838   }
 839   return Changed;
 840 }
 841
 842
 843 // RaisePointerReferences::doit - Raise a method representation to a higher
 844 // level.
 845 //
 846 bool RaisePointerReferences::doit(Method *M) {
 847   if (M->isExternal()) return false;
 848   bool Changed = false;
 849
 850 #ifdef DEBUG_PEEPHOLE_INSTS
 851   cerr << "\n\n\nStarting to work on Method '" << M->getName() << "'\n";
 852 #endif
 853
 854   while (DoRaisePass(M)) Changed = true;
 855
 856   // PtrCasts - Keep a mapping between the pointer values (the key of the
 857   // map), and the cast to array pointer (the value) in this map.  This is
 858   // used when converting pointer math into array addressing.
 859   //
 860   map<Value*, CastInst*> PtrCasts;
 861
 862   // Insert casts for all incoming pointer values.  Keep track of those casts
 863   // and the identified incoming values in the PtrCasts map.
 864   //
 865   Changed |= DoInsertArrayCasts(M, PtrCasts);
 866
 867   // Loop over each incoming pointer variable, replacing indexing arithmetic
 868   // with getelementptr calls.
 869   //
 870   Changed |= reduce_apply_bool(PtrCasts.begin(), PtrCasts.end(),
 871                                ptr_fun(DoEliminatePointerArithmetic));
 872
 873   return Changed;
 874 }