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.
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/Transforms/LevelChange.h"
  10 #include "llvm/Transforms/Utils/Local.h"
  11 #include "TransformInternals.h"
  12 #include "llvm/iOther.h"
  13 #include "llvm/iMemory.h"
  14 #include "llvm/Pass.h"
  15 #include "llvm/ConstantHandling.h"
  16 #include "llvm/Analysis/Expressions.h"
  17 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  18 #include "Support/STLExtras.h"
  19 #include "Support/StatisticReporter.h"
  20 #include <algorithm>
  21
  22 static Statistic<> NumLoadStorePeepholes("raise\t\t- Number of load/store peepholes");
  23 static Statistic<> NumGEPInstFormed("raise\t\t- Number of other getelementptr's formed");
  24 static Statistic<> NumExprTreesConv("raise\t\t- Number of expression trees converted");
  25 static Statistic<> NumCastOfCast("raise\t\t- Number of cast-of-self removed");
  26 static Statistic<> NumDCEorCP("raise\t\t- Number of insts DCE'd or constprop'd");
  27
  28
  29 //#define DEBUG_PEEPHOLE_INSTS 1
  30
  31 #ifdef DEBUG_PEEPHOLE_INSTS
  32 #define PRINT_PEEPHOLE(ID, NUM, I)            \
  33   std::cerr << "Inst P/H " << ID << "[" << NUM << "] " << I;
  34 #else
  35 #define PRINT_PEEPHOLE(ID, NUM, I)
  36 #endif
  37
  38 #define PRINT_PEEPHOLE1(ID, I1) do { PRINT_PEEPHOLE(ID, 0, I1); } while (0)
  39 #define PRINT_PEEPHOLE2(ID, I1, I2) \
  40   do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); } while (0)
  41 #define PRINT_PEEPHOLE3(ID, I1, I2, I3) \
  42   do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); \
  43        PRINT_PEEPHOLE(ID, 2, I3); } while (0)
  44 #define PRINT_PEEPHOLE4(ID, I1, I2, I3, I4) \
  45   do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); \
  46        PRINT_PEEPHOLE(ID, 2, I3); PRINT_PEEPHOLE(ID, 3, I4); } while (0)
  47
  48
  49 // isReinterpretingCast - Return true if the cast instruction specified will
  50 // cause the operand to be "reinterpreted".  A value is reinterpreted if the
  51 // cast instruction would cause the underlying bits to change.
  52 //
  53 static inline bool isReinterpretingCast(const CastInst *CI) {
  54   return!CI->getOperand(0)->getType()->isLosslesslyConvertableTo(CI->getType());
  55 }
  56
  57
  58 // Peephole optimize the following instructions:
  59 // %t1 = cast ? to x *
  60 // %t2 = add x * %SP, %t1              ;; Constant must be 2nd operand
  61 //
  62 // Into: %t3 = getelementptr {<...>} * %SP, <element indices>
  63 //       %t2 = cast <eltype> * %t3 to {<...>}*
  64 //
  65 static bool HandleCastToPointer(BasicBlock::iterator BI,
  66                                 const PointerType *DestPTy) {
  67   CastInst *CI = cast<CastInst>(*BI);
  68   if (CI->use_empty()) return false;
  69
  70   // Scan all of the uses, looking for any uses that are not add
  71   // instructions.  If we have non-adds, do not make this transformation.
  72   //
  73   for (Value::use_iterator I = CI->use_begin(), E = CI->use_end();
  74        I != E; ++I) {
  75     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(*I)) {
  76       if (BO->getOpcode() != Instruction::Add)
  77         return false;
  78     } else {
  79       return false;
  80     }
  81   }
  82
  83   std::vector<Value*> Indices;
  84   Value *Src = CI->getOperand(0);
  85   const Type *Result = ConvertableToGEP(DestPTy, Src, Indices, &BI);
  86   if (Result == 0) return false;  // Not convertable...
  87
  88   PRINT_PEEPHOLE2("cast-add-to-gep:in", Src, CI);
  89
  90   // If we have a getelementptr capability... transform all of the
  91   // add instruction uses into getelementptr's.
  92   while (!CI->use_empty()) {
  93     BinaryOperator *I = cast<BinaryOperator>(*CI->use_begin());
  94     assert(I->getOpcode() == Instruction::Add && I->getNumOperands() == 2 &&
  95            "Use is not a valid add instruction!");
  96
  97     // Get the value added to the cast result pointer...
  98     Value *OtherPtr = I->getOperand((I->getOperand(0) == CI) ? 1 : 0);
  99
 100     Instruction *GEP = new GetElementPtrInst(OtherPtr, Indices, I->getName());
 101     PRINT_PEEPHOLE1("cast-add-to-gep:i", I);
 102
 103     if (GEP->getType() == I->getType()) {
 104       // Replace the old add instruction with the shiny new GEP inst
 105       ReplaceInstWithInst(I, GEP);
 106     } else {
 107       // If the type produced by the gep instruction differs from the original
 108       // add instruction type, insert a cast now.
 109       //
 110
 111       // Insert the GEP instruction before the old add instruction... and get an
 112       // iterator to point at the add instruction...
 113       BasicBlock::iterator GEPI = InsertInstBeforeInst(GEP, I)+1;
 114
 115       PRINT_PEEPHOLE1("cast-add-to-gep:o", GEP);
 116       CastInst *CI = new CastInst(GEP, I->getType());
 117       GEP = CI;
 118
 119       // Replace the old add instruction with the shiny new GEP inst
 120       ReplaceInstWithInst(I->getParent()->getInstList(), GEPI, GEP);
 121     }
 122
 123     PRINT_PEEPHOLE1("cast-add-to-gep:o", GEP);
 124   }
 125   return true;
 126 }
 127
 128 // Peephole optimize the following instructions:
 129 // %t1 = cast ulong <const int> to {<...>} *
 130 // %t2 = add {<...>} * %SP, %t1              ;; Constant must be 2nd operand
 131 //
 132 //    or
 133 // %t1 = cast {<...>}* %SP to int*
 134 // %t5 = cast ulong <const int> to int*
 135 // %t2 = add int* %t1, %t5                   ;; int is same size as field
 136 //
 137 // Into: %t3 = getelementptr {<...>} * %SP, <element indices>
 138 //       %t2 = cast <eltype> * %t3 to {<...>}*
 139 //
 140 static bool PeepholeOptimizeAddCast(BasicBlock *BB, BasicBlock::iterator &BI,
 141                                     Value *AddOp1, CastInst *AddOp2) {
 142   const CompositeType *CompTy;
 143   Value *OffsetVal = AddOp2->getOperand(0);
 144   Value *SrcPtr;  // Of type pointer to struct...
 145
 146   if ((CompTy = getPointedToComposite(AddOp1->getType()))) {
 147     SrcPtr = AddOp1;                      // Handle the first case...
 148   } else if (CastInst *AddOp1c = dyn_cast<CastInst>(AddOp1)) {
 149     SrcPtr = AddOp1c->getOperand(0);      // Handle the second case...
 150     CompTy = getPointedToComposite(SrcPtr->getType());
 151   }
 152
 153   // Only proceed if we have detected all of our conditions successfully...
 154   if (!CompTy || !SrcPtr || !OffsetVal->getType()->isIntegral())
 155     return false;
 156
 157   std::vector<Value*> Indices;
 158   if (!ConvertableToGEP(SrcPtr->getType(), OffsetVal, Indices, &BI))
 159     return false;  // Not convertable... perhaps next time
 160
 161   if (getPointedToComposite(AddOp1->getType())) {  // case 1
 162     PRINT_PEEPHOLE2("add-to-gep1:in", AddOp2, *BI);
 163   } else {
 164     PRINT_PEEPHOLE3("add-to-gep2:in", AddOp1, AddOp2, *BI);
 165   }
 166
 167   GetElementPtrInst *GEP = new GetElementPtrInst(SrcPtr, Indices,
 168                                                  AddOp2->getName());
 169   BI = BB->getInstList().insert(BI, GEP)+1;
 170
 171   Instruction *NCI = new CastInst(GEP, AddOp1->getType());
 172   ReplaceInstWithInst(BB->getInstList(), BI, NCI);
 173   PRINT_PEEPHOLE2("add-to-gep:out", GEP, NCI);
 174   return true;
 175 }
 176
 177 static bool PeepholeOptimize(BasicBlock *BB, BasicBlock::iterator &BI) {
 178   Instruction *I = *BI;
 179
 180   if (CastInst *CI = dyn_cast<CastInst>(I)) {
 181     Value       *Src    = CI->getOperand(0);
 182     Instruction *SrcI   = dyn_cast<Instruction>(Src); // Nonnull if instr source
 183     const Type  *DestTy = CI->getType();
 184
 185     // Peephole optimize the following instruction:
 186     // %V2 = cast <ty> %V to <ty>
 187     //
 188     // Into: <nothing>
 189     //
 190     if (DestTy == Src->getType()) {   // Check for a cast to same type as src!!
 191       PRINT_PEEPHOLE1("cast-of-self-ty", CI);
 192       CI->replaceAllUsesWith(Src);
 193       if (!Src->hasName() && CI->hasName()) {
 194         std::string Name = CI->getName();
 195         CI->setName("");
 196         Src->setName(Name, BB->getParent()->getSymbolTable());
 197       }
 198
 199       // DCE the instruction now, to avoid having the iterative version of DCE
 200       // have to worry about it.
 201       //
 202       delete BB->getInstList().remove(BI);
 203
 204       ++NumCastOfCast;
 205       return true;
 206     }
 207
 208     // Check to see if it's a cast of an instruction that does not depend on the
 209     // specific type of the operands to do it's job.
 210     if (!isReinterpretingCast(CI)) {
 211       ValueTypeCache ConvertedTypes;
 212
 213       // Check to see if we can convert the users of the cast value to match the
 214       // source type of the cast...
 215       //
 216       ConvertedTypes[CI] = CI->getType();  // Make sure the cast doesn't change
 217       if (ExpressionConvertableToType(Src, DestTy, ConvertedTypes)) {
 218         PRINT_PEEPHOLE3("CAST-SRC-EXPR-CONV:in ", Src, CI, BB->getParent());
 219
 220 #ifdef DEBUG_PEEPHOLE_INSTS
 221         cerr << "\nCONVERTING SRC EXPR TYPE:\n";
 222 #endif
 223         ValueMapCache ValueMap;
 224         Value *E = ConvertExpressionToType(Src, DestTy, ValueMap);
 225         if (Constant *CPV = dyn_cast<Constant>(E))
 226           CI->replaceAllUsesWith(CPV);
 227
 228         BI = BB->begin();  // Rescan basic block.  BI might be invalidated.
 229         PRINT_PEEPHOLE1("CAST-SRC-EXPR-CONV:out", E);
 230 #ifdef DEBUG_PEEPHOLE_INSTS
 231         cerr << "DONE CONVERTING SRC EXPR TYPE: \n" << BB->getParent();
 232 #endif
 233         ++NumExprTreesConv;
 234         return true;
 235       }
 236
 237       // Check to see if we can convert the source of the cast to match the
 238       // destination type of the cast...
 239       //
 240       ConvertedTypes.clear();
 241       if (ValueConvertableToType(CI, Src->getType(), ConvertedTypes)) {
 242         PRINT_PEEPHOLE3("CAST-DEST-EXPR-CONV:in ", Src, CI, BB->getParent());
 243
 244 #ifdef DEBUG_PEEPHOLE_INSTS
 245         cerr << "\nCONVERTING EXPR TYPE:\n";
 246 #endif
 247         ValueMapCache ValueMap;
 248         ConvertValueToNewType(CI, Src, ValueMap);  // This will delete CI!
 249
 250         BI = BB->begin();  // Rescan basic block.  BI might be invalidated.
 251         PRINT_PEEPHOLE1("CAST-DEST-EXPR-CONV:out", Src);
 252 #ifdef DEBUG_PEEPHOLE_INSTS
 253         cerr << "DONE CONVERTING EXPR TYPE: \n\n" << BB->getParent();
 254 #endif
 255         ++NumExprTreesConv;
 256         return true;
 257       }
 258     }
 259
 260     // Otherwise find out it this cast is a cast to a pointer type, which is
 261     // then added to some other pointer, then loaded or stored through.  If
 262     // so, convert the add into a getelementptr instruction...
 263     //
 264     if (const PointerType *DestPTy = dyn_cast<PointerType>(DestTy)) {
 265       if (HandleCastToPointer(BI, DestPTy)) {
 266         BI = BB->begin();  // Rescan basic block.  BI might be invalidated.
 267         ++NumGEPInstFormed;
 268         return true;
 269       }
 270     }
 271
 272     // Check to see if we are casting from a structure pointer to a pointer to
 273     // the first element of the structure... to avoid munching other peepholes,
 274     // we only let this happen if there are no add uses of the cast.
 275     //
 276     // Peephole optimize the following instructions:
 277     // %t1 = cast {<...>} * %StructPtr to <ty> *
 278     //
 279     // Into: %t2 = getelementptr {<...>} * %StructPtr, <0, 0, 0, ...>
 280     //       %t1 = cast <eltype> * %t1 to <ty> *
 281     //
 282 #if 1
 283     if (const CompositeType *CTy = getPointedToComposite(Src->getType()))
 284       if (const PointerType *DestPTy = dyn_cast<PointerType>(DestTy)) {
 285
 286         // Loop over uses of the cast, checking for add instructions.  If an add
 287         // exists, this is probably a part of a more complex GEP, so we don't
 288         // want to mess around with the cast.
 289         //
 290         bool HasAddUse = false;
 291         for (Value::use_iterator I = CI->use_begin(), E = CI->use_end();
 292              I != E; ++I)
 293           if (isa<Instruction>(*I) &&
 294               cast<Instruction>(*I)->getOpcode() == Instruction::Add) {
 295             HasAddUse = true; break;
 296           }
 297
 298         // If it doesn't have an add use, check to see if the dest type is
 299         // losslessly convertable to one of the types in the start of the struct
 300         // type.
 301         //
 302         if (!HasAddUse) {
 303           const Type *DestPointedTy = DestPTy->getElementType();
 304           unsigned Depth = 1;
 305           const CompositeType *CurCTy = CTy;
 306           const Type *ElTy = 0;
 307
 308           // Build the index vector, full of all zeros
 309           std::vector<Value*> Indices;
 310           Indices.push_back(ConstantUInt::get(Type::UIntTy, 0));
 311           while (CurCTy && !isa<PointerType>(CurCTy)) {
 312             if (const StructType *CurSTy = dyn_cast<StructType>(CurCTy)) {
 313               // Check for a zero element struct type... if we have one, bail.
 314               if (CurSTy->getElementTypes().size() == 0) break;
 315
 316               // Grab the first element of the struct type, which must lie at
 317               // offset zero in the struct.
 318               //
 319               ElTy = CurSTy->getElementTypes()[0];
 320             } else {
 321               ElTy = cast<ArrayType>(CurCTy)->getElementType();
 322             }
 323
 324             // Insert a zero to index through this type...
 325             Indices.push_back(ConstantUInt::get(CurCTy->getIndexType(), 0));
 326
 327             // Did we find what we're looking for?
 328             if (ElTy->isLosslesslyConvertableTo(DestPointedTy)) break;
 329
 330             // Nope, go a level deeper.
 331             ++Depth;
 332             CurCTy = dyn_cast<CompositeType>(ElTy);
 333             ElTy = 0;
 334           }
 335
 336           // Did we find what we were looking for? If so, do the transformation
 337           if (ElTy) {
 338             PRINT_PEEPHOLE1("cast-for-first:in", CI);
 339
 340             // Insert the new T cast instruction... stealing old T's name
 341             GetElementPtrInst *GEP = new GetElementPtrInst(Src, Indices,
 342                                                            CI->getName());
 343             CI->setName("");
 344             BI = BB->getInstList().insert(BI, GEP)+1;
 345
 346             // Make the old cast instruction reference the new GEP instead of
 347             // the old src value.
 348             //
 349             CI->setOperand(0, GEP);
 350
 351             PRINT_PEEPHOLE2("cast-for-first:out", GEP, CI);
 352             ++NumGEPInstFormed;
 353             return true;
 354           }
 355         }
 356       }
 357 #endif
 358
 359 #if 1
 360   } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 361     Value *Val     = SI->getOperand(0);
 362     Value *Pointer = SI->getPointerOperand();
 363
 364     // Peephole optimize the following instructions:
 365     // %t = cast <T1>* %P to <T2> * ;; If T1 is losslessly convertable to T2
 366     // store <T2> %V, <T2>* %t
 367     //
 368     // Into:
 369     // %t = cast <T2> %V to <T1>
 370     // store <T1> %t2, <T1>* %P
 371     //
 372     // Note: This is not taken care of by expr conversion because there might
 373     // not be a cast available for the store to convert the incoming value of.
 374     // This code is basically here to make sure that pointers don't have casts
 375     // if possible.
 376     //
 377     if (CastInst *CI = dyn_cast<CastInst>(Pointer))
 378       if (Value *CastSrc = CI->getOperand(0)) // CSPT = CastSrcPointerType
 379         if (PointerType *CSPT = dyn_cast<PointerType>(CastSrc->getType()))
 380           // convertable types?
 381           if (Val->getType()->isLosslesslyConvertableTo(CSPT->getElementType()) &&
 382               !SI->hasIndices()) {      // No subscripts yet!
 383             PRINT_PEEPHOLE3("st-src-cast:in ", Pointer, Val, SI);
 384
 385             // Insert the new T cast instruction... stealing old T's name
 386             CastInst *NCI = new CastInst(Val, CSPT->getElementType(),
 387                                          CI->getName());
 388             CI->setName("");
 389             BI = BB->getInstList().insert(BI, NCI)+1;
 390
 391             // Replace the old store with a new one!
 392             ReplaceInstWithInst(BB->getInstList(), BI,
 393                                 SI = new StoreInst(NCI, CastSrc));
 394             PRINT_PEEPHOLE3("st-src-cast:out", NCI, CastSrc, SI);
 395             ++NumLoadStorePeepholes;
 396             return true;
 397           }
 398
 399   } else if (I->getOpcode() == Instruction::Add &&
 400              isa<CastInst>(I->getOperand(1))) {
 401
 402     if (PeepholeOptimizeAddCast(BB, BI, I->getOperand(0),
 403                                 cast<CastInst>(I->getOperand(1)))) {
 404       ++NumGEPInstFormed;
 405       return true;
 406     }
 407 #endif
 408   }
 409
 410   return false;
 411 }
 412
 413
 414
 415
 416 static bool DoRaisePass(Function *F) {
 417   bool Changed = false;
 418   for (Function::iterator MI = F->begin(), ME = F->end(); MI != ME; ++MI) {
 419     BasicBlock *BB = *MI;
 420     BasicBlock::InstListType &BIL = BB->getInstList();
 421
 422     for (BasicBlock::iterator BI = BB->begin(); BI != BB->end();) {
 423 #if DEBUG_PEEPHOLE_INSTS
 424       cerr << "Processing: " << *BI;
 425 #endif
 426       if (dceInstruction(BIL, BI) || doConstantPropogation(BB, BI)) {
 427         Changed = true;
 428         ++NumDCEorCP;
 429 #ifdef DEBUG_PEEPHOLE_INSTS
 430         cerr << "***\t\t^^-- DeadCode Elinated!\n";
 431 #endif
 432       } else if (PeepholeOptimize(BB, BI))
 433         Changed = true;
 434       else
 435         ++BI;
 436     }
 437   }
 438   return Changed;
 439 }
 440
 441
 442 // RaisePointerReferences::doit - Raise a function representation to a higher
 443 // level.
 444 //
 445 static bool doRPR(Function *F) {
 446 #ifdef DEBUG_PEEPHOLE_INSTS
 447   cerr << "\n\n\nStarting to work on Function '" << F->getName() << "'\n";
 448 #endif
 449
 450   // Insert casts for all incoming pointer pointer values that are treated as
 451   // arrays...
 452   //
 453   bool Changed = false, LocalChange;
 454
 455   do {
 456 #ifdef DEBUG_PEEPHOLE_INSTS
 457     cerr << "Looping: \n" << F;
 458 #endif
 459
 460     // Iterate over the function, refining it, until it converges on a stable
 461     // state
 462     LocalChange = false;
 463     while (DoRaisePass(F)) LocalChange = true;
 464     Changed |= LocalChange;
 465
 466   } while (LocalChange);
 467
 468   return Changed;
 469 }
 470
 471 namespace {
 472   struct RaisePointerReferences : public FunctionPass {
 473     const char *getPassName() const { return "Raise Pointer References"; }
 474
 475     virtual bool runOnFunction(Function *F) { return doRPR(F); }
 476
 477     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 478       AU.preservesCFG();
 479     }
 480   };
 481 }
 482
 483 Pass *createRaisePointerReferencesPass() {
 484   return new RaisePointerReferences();
 485 }
 486
 487