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