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/Method.h"
  12 #include "llvm/Support/STLExtras.h"
  13 #include "llvm/iOther.h"
  14 #include "llvm/iMemory.h"
  15 #include "llvm/ConstPoolVals.h"
  16 #include "llvm/Optimizations/ConstantHandling.h"
  17 #include "llvm/Optimizations/DCE.h"
  18 #include "llvm/Analysis/Expressions.h"
  19 #include <algorithm>
  20
  21 #include "llvm/Assembly/Writer.h"
  22
  23 #define DEBUG_PEEPHOLE_INSTS 1
  24
  25 #ifdef DEBUG_PEEPHOLE_INSTS
  26 #define PRINT_PEEPHOLE(ID, NUM, I)            \
  27   cerr << "Inst P/H " << ID << "[" << NUM << "] " << I;
  28 #else
  29 #define PRINT_PEEPHOLE(ID, NUM, I)
  30 #endif
  31
  32 #define PRINT_PEEPHOLE1(ID, I1) do { PRINT_PEEPHOLE(ID, 0, I1); } while (0)
  33 #define PRINT_PEEPHOLE2(ID, I1, I2) \
  34   do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); } while (0)
  35 #define PRINT_PEEPHOLE3(ID, I1, I2, I3) \
  36   do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); \
  37        PRINT_PEEPHOLE(ID, 2, I3); } while (0)
  38 #define PRINT_PEEPHOLE4(ID, I1, I2, I3, I4) \
  39   do { PRINT_PEEPHOLE(ID, 0, I1); PRINT_PEEPHOLE(ID, 1, I2); \
  40        PRINT_PEEPHOLE(ID, 2, I3); PRINT_PEEPHOLE(ID, 3, I4); } while (0)
  41
  42
  43 // isReinterpretingCast - Return true if the cast instruction specified will
  44 // cause the operand to be "reinterpreted".  A value is reinterpreted if the
  45 // cast instruction would cause the underlying bits to change.
  46 //
  47 static inline bool isReinterpretingCast(const CastInst *CI) {
  48   return!CI->getOperand(0)->getType()->isLosslesslyConvertableTo(CI->getType());
  49 }
  50
  51
  52
  53
  54
  55 // Peephole optimize the following instructions:
  56 // %t1 = cast ulong <const int> to {<...>} *
  57 // %t2 = add {<...>} * %SP, %t1              ;; Constant must be 2nd operand
  58 //
  59 //    or
  60 // %t1 = cast {<...>}* %SP to int*
  61 // %t5 = cast ulong <const int> to int*
  62 // %t2 = add int* %t1, %t5                   ;; int is same size as field
  63 //
  64 // Into: %t3 = getelementptr {<...>} * %SP, <element indices>
  65 //       %t2 = cast <eltype> * %t3 to {<...>}*
  66 //
  67 static bool PeepholeOptimizeAddCast(BasicBlock *BB, BasicBlock::iterator &BI,
  68                                     Value *AddOp1, CastInst *AddOp2) {
  69   const CompositeType *CompTy;
  70   Value *OffsetVal = AddOp2->getOperand(0);
  71   Value *SrcPtr;  // Of type pointer to struct...
  72
  73   if ((CompTy = getPointedToComposite(AddOp1->getType()))) {
  74     SrcPtr = AddOp1;                      // Handle the first case...
  75   } else if (CastInst *AddOp1c = dyn_cast<CastInst>(AddOp1)) {
  76     SrcPtr = AddOp1c->getOperand(0);      // Handle the second case...
  77     CompTy = getPointedToComposite(SrcPtr->getType());
  78   }
  79
  80   // Only proceed if we have detected all of our conditions successfully...
  81   if (!CompTy || !SrcPtr || !OffsetVal->getType()->isIntegral())
  82     return false;
  83
  84   vector<Value*> Indices;
  85   if (!ConvertableToGEP(SrcPtr->getType(), OffsetVal, Indices, &BI))
  86     return false;  // Not convertable... perhaps next time
  87
  88   if (getPointedToComposite(AddOp1->getType())) {  // case 1
  89     PRINT_PEEPHOLE2("add-to-gep1:in", AddOp2, *BI);
  90   } else {
  91     PRINT_PEEPHOLE3("add-to-gep2:in", AddOp1, AddOp2, *BI);
  92   }
  93
  94   GetElementPtrInst *GEP = new GetElementPtrInst(SrcPtr, Indices,
  95                                                  AddOp2->getName());
  96   BI = BB->getInstList().insert(BI, GEP)+1;
  97
  98   Instruction *NCI = new CastInst(GEP, AddOp1->getType());
  99   ReplaceInstWithInst(BB->getInstList(), BI, NCI);
 100   PRINT_PEEPHOLE2("add-to-gep:out", GEP, NCI);
 101   return true;
 102 }
 103
 104 static bool PeepholeOptimize(BasicBlock *BB, BasicBlock::iterator &BI) {
 105   Instruction *I = *BI;
 106
 107   if (CastInst *CI = dyn_cast<CastInst>(I)) {
 108     Value       *Src    = CI->getOperand(0);
 109     Instruction *SrcI   = dyn_cast<Instruction>(Src); // Nonnull if instr source
 110     const Type  *DestTy = CI->getType();
 111
 112     // Peephole optimize the following instruction:
 113     // %V2 = cast <ty> %V to <ty>
 114     //
 115     // Into: <nothing>
 116     //
 117     if (DestTy == Src->getType()) {   // Check for a cast to same type as src!!
 118       PRINT_PEEPHOLE1("cast-of-self-ty", CI);
 119       CI->replaceAllUsesWith(Src);
 120       if (!Src->hasName() && CI->hasName()) {
 121         string Name = CI->getName();
 122         CI->setName("");
 123         Src->setName(Name, BB->getParent()->getSymbolTable());
 124       }
 125       return true;
 126     }
 127
 128     // Peephole optimize the following instructions:
 129     // %tmp = cast <ty> %V to <ty2>
 130     // %V  = cast <ty2> %tmp to <ty3>     ; Where ty & ty2 are same size
 131     //
 132     // Into: cast <ty> %V to <ty3>
 133     //
 134     if (SrcI)
 135       if (CastInst *CSrc = dyn_cast<CastInst>(SrcI))
 136         if (isReinterpretingCast(CI) + isReinterpretingCast(CSrc) < 2) {
 137           // We can only do c-c elimination if, at most, one cast does a
 138           // reinterpretation of the input data.
 139           //
 140           // If legal, make this cast refer the the original casts argument!
 141           //
 142           PRINT_PEEPHOLE2("cast-cast:in ", CI, CSrc);
 143           CI->setOperand(0, CSrc->getOperand(0));
 144           PRINT_PEEPHOLE1("cast-cast:out", CI);
 145           return true;
 146         }
 147
 148     // Check to see if it's a cast of an instruction that does not depend on the
 149     // specific type of the operands to do it's job.
 150     if (!isReinterpretingCast(CI)) {
 151       ValueTypeCache ConvertedTypes;
 152       if (ValueConvertableToType(CI, Src->getType(), ConvertedTypes)) {
 153         PRINT_PEEPHOLE2("CAST-DEST-EXPR-CONV:in ", Src, CI);
 154
 155 #ifdef DEBUG_PEEPHOLE_INSTS
 156         cerr << "\nCONVERTING EXPR TYPE:\n";
 157 #endif
 158         ValueMapCache ValueMap;
 159         ConvertValueToNewType(CI, Src, ValueMap);  // This will delete CI!
 160
 161         BI = BB->begin();  // Rescan basic block.  BI might be invalidated.
 162         PRINT_PEEPHOLE1("CAST-DEST-EXPR-CONV:out", Src);
 163 #ifdef DEBUG_PEEPHOLE_INSTS
 164         cerr << "DONE CONVERTING EXPR TYPE: \n\n";// << BB->getParent();
 165 #endif
 166         return true;
 167       } else {
 168         ConvertedTypes.clear();
 169         if (ExpressionConvertableToType(Src, DestTy, ConvertedTypes)) {
 170           PRINT_PEEPHOLE2("CAST-SRC-EXPR-CONV:in ", Src, CI);
 171
 172 #ifdef DEBUG_PEEPHOLE_INSTS
 173           cerr << "\nCONVERTING SRC EXPR TYPE:\n";
 174 #endif
 175           ValueMapCache ValueMap;
 176           Value *E = ConvertExpressionToType(Src, DestTy, ValueMap);
 177           if (ConstPoolVal *CPV = dyn_cast<ConstPoolVal>(E))
 178             CI->replaceAllUsesWith(CPV);
 179
 180           BI = BB->begin();  // Rescan basic block.  BI might be invalidated.
 181           PRINT_PEEPHOLE1("CAST-SRC-EXPR-CONV:out", E);
 182 #ifdef DEBUG_PEEPHOLE_INSTS
 183           cerr << "DONE CONVERTING SRC EXPR TYPE: \n\n";// << BB->getParent();
 184 #endif
 185           return true;
 186         }
 187       }
 188
 189     }
 190
 191     // Check to see if we are casting from a structure pointer to a pointer to
 192     // the first element of the structure... to avoid munching other peepholes,
 193     // we only let this happen if there are no add uses of the cast.
 194     //
 195     // Peephole optimize the following instructions:
 196     // %t1 = cast {<...>} * %StructPtr to <ty> *
 197     //
 198     // Into: %t2 = getelementptr {<...>} * %StructPtr, <0, 0, 0, ...>
 199     //       %t1 = cast <eltype> * %t1 to <ty> *
 200     //
 201 #if 1
 202     if (const CompositeType *CTy = getPointedToComposite(Src->getType()))
 203       if (const PointerType *DestPTy = dyn_cast<PointerType>(DestTy)) {
 204
 205         // Loop over uses of the cast, checking for add instructions.  If an add
 206         // exists, this is probably a part of a more complex GEP, so we don't
 207         // want to mess around with the cast.
 208         //
 209         bool HasAddUse = false;
 210         for (Value::use_iterator I = CI->use_begin(), E = CI->use_end();
 211              I != E; ++I)
 212           if (isa<Instruction>(*I) &&
 213               cast<Instruction>(*I)->getOpcode() == Instruction::Add) {
 214             HasAddUse = true; break;
 215           }
 216
 217         // If it doesn't have an add use, check to see if the dest type is
 218         // losslessly convertable to one of the types in the start of the struct
 219         // type.
 220         //
 221         if (!HasAddUse) {
 222           const Type *DestPointedTy = DestPTy->getValueType();
 223           unsigned Depth = 1;
 224           const CompositeType *CurCTy = CTy;
 225           const Type *ElTy = 0;
 226
 227           // Build the index vector, full of all zeros
 228           vector<Value*> Indices;
 229
 230           while (CurCTy) {
 231             if (const StructType *CurSTy = dyn_cast<StructType>(CurCTy)) {
 232               // Check for a zero element struct type... if we have one, bail.
 233               if (CurSTy->getElementTypes().size() == 0) break;
 234
 235               // Grab the first element of the struct type, which must lie at
 236               // offset zero in the struct.
 237               //
 238               ElTy = CurSTy->getElementTypes()[0];
 239             } else {
 240               ElTy = cast<ArrayType>(CurCTy)->getElementType();
 241             }
 242
 243             // Insert a zero to index through this type...
 244             Indices.push_back(ConstPoolUInt::get(CurCTy->getIndexType(), 0));
 245
 246             // Did we find what we're looking for?
 247             if (ElTy->isLosslesslyConvertableTo(DestPointedTy)) break;
 248
 249             // Nope, go a level deeper.
 250             ++Depth;
 251             CurCTy = dyn_cast<CompositeType>(ElTy);
 252             ElTy = 0;
 253           }
 254
 255           // Did we find what we were looking for? If so, do the transformation
 256           if (ElTy) {
 257             PRINT_PEEPHOLE1("cast-for-first:in", CI);
 258
 259             // Insert the new T cast instruction... stealing old T's name
 260             GetElementPtrInst *GEP = new GetElementPtrInst(Src, Indices,
 261                                                            CI->getName());
 262             CI->setName("");
 263             BI = BB->getInstList().insert(BI, GEP)+1;
 264
 265             // Make the old cast instruction reference the new GEP instead of
 266             // the old src value.
 267             //
 268             CI->setOperand(0, GEP);
 269
 270             PRINT_PEEPHOLE2("cast-for-first:out", GEP, CI);
 271             return true;
 272           }
 273         }
 274       }
 275 #endif
 276
 277 #if 1
 278   } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 279     Value *Val     = SI->getOperand(0);
 280     Value *Pointer = SI->getPointerOperand();
 281
 282     // Peephole optimize the following instructions:
 283     // %t1 = getelementptr {<...>} * %StructPtr, <element indices>
 284     // store <elementty> %v, <elementty> * %t1
 285     //
 286     // Into: store <elementty> %v, {<...>} * %StructPtr, <element indices>
 287     //
 288     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Pointer)) {
 289       // Append any indices that the store instruction has onto the end of the
 290       // ones that the GEP is carrying...
 291       //
 292       vector<Value*> Indices(GEP->copyIndices());
 293       Indices.insert(Indices.end(), SI->idx_begin(), SI->idx_end());
 294
 295       PRINT_PEEPHOLE2("gep-store:in", GEP, SI);
 296       ReplaceInstWithInst(BB->getInstList(), BI,
 297                           SI = new StoreInst(Val, GEP->getPointerOperand(),
 298                                              Indices));
 299       PRINT_PEEPHOLE1("gep-store:out", SI);
 300       return true;
 301     }
 302
 303     // Peephole optimize the following instructions:
 304     // %t = cast <T1>* %P to <T2> * ;; If T1 is losslessly convertable to T2
 305     // store <T2> %V, <T2>* %t
 306     //
 307     // Into:
 308     // %t = cast <T2> %V to <T1>
 309     // store <T1> %t2, <T1>* %P
 310     //
 311     if (CastInst *CI = dyn_cast<CastInst>(Pointer))
 312       if (Value *CastSrc = CI->getOperand(0)) // CSPT = CastSrcPointerType
 313         if (PointerType *CSPT = dyn_cast<PointerType>(CastSrc->getType()))
 314           // convertable types?
 315           if (Val->getType()->isLosslesslyConvertableTo(CSPT->getValueType()) &&
 316               !SI->hasIndices()) {      // No subscripts yet!
 317             PRINT_PEEPHOLE3("st-src-cast:in ", Pointer, Val, SI);
 318
 319             // Insert the new T cast instruction... stealing old T's name
 320             CastInst *NCI = new CastInst(Val, CSPT->getValueType(),
 321                                          CI->getName());
 322             CI->setName("");
 323             BI = BB->getInstList().insert(BI, NCI)+1;
 324
 325             // Replace the old store with a new one!
 326             ReplaceInstWithInst(BB->getInstList(), BI,
 327                                 SI = new StoreInst(NCI, CastSrc));
 328             PRINT_PEEPHOLE3("st-src-cast:out", NCI, CastSrc, SI);
 329             return true;
 330           }
 331
 332
 333   } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
 334     Value *Pointer = LI->getPointerOperand();
 335
 336     // Peephole optimize the following instructions:
 337     // %t1 = getelementptr {<...>} * %StructPtr, <element indices>
 338     // %V  = load <elementty> * %t1
 339     //
 340     // Into: load {<...>} * %StructPtr, <element indices>
 341     //
 342     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Pointer)) {
 343       // Append any indices that the load instruction has onto the end of the
 344       // ones that the GEP is carrying...
 345       //
 346       vector<Value*> Indices(GEP->copyIndices());
 347       Indices.insert(Indices.end(), LI->idx_begin(), LI->idx_end());
 348
 349       PRINT_PEEPHOLE2("gep-load:in", GEP, LI);
 350       ReplaceInstWithInst(BB->getInstList(), BI,
 351                           LI = new LoadInst(GEP->getPointerOperand(),
 352                                             Indices));
 353       PRINT_PEEPHOLE1("gep-load:out", LI);
 354       return true;
 355     }
 356
 357
 358     // Peephole optimize the following instructions:
 359     // %t1 = cast <ty> * %t0 to <ty2> *
 360     // %V  = load <ty2> * %t1
 361     //
 362     // Into: %t1 = load <ty> * %t0
 363     //       %V  = cast <ty> %t1 to <ty2>
 364     //
 365     // The idea behind this transformation is that if the expression type
 366     // conversion engine could not convert the cast into some other nice form,
 367     // that there is something fundementally wrong with the current shape of
 368     // the program.  Move the cast through the load and try again.  This will
 369     // leave the original cast instruction, to presumably become dead.
 370     //
 371     if (CastInst *CI = dyn_cast<CastInst>(Pointer)) {
 372       Value *SrcVal = CI->getOperand(0);
 373       const PointerType *SrcTy = dyn_cast<PointerType>(SrcVal->getType());
 374       const Type *ElTy = SrcTy ? SrcTy->getValueType() : 0;
 375
 376       // Make sure that nothing will be lost in the new cast...
 377       if (!LI->hasIndices() && SrcTy &&
 378           ElTy->isLosslesslyConvertableTo(LI->getType())) {
 379         PRINT_PEEPHOLE2("CL-LoadCast:in ", CI, LI);
 380
 381         string CName = CI->getName(); CI->setName("");
 382         LoadInst *NLI = new LoadInst(SrcVal, LI->getName());
 383         LI->setName("");  // Take over the old load's name
 384
 385         // Insert the load before the old load
 386         BI = BB->getInstList().insert(BI, NLI)+1;
 387
 388         // Replace the old load with a new cast...
 389         ReplaceInstWithInst(BB->getInstList(), BI,
 390                             CI = new CastInst(NLI, LI->getType(), CName));
 391         PRINT_PEEPHOLE2("CL-LoadCast:out", NLI, CI);
 392
 393         return true;
 394       }
 395     }
 396   } else if (I->getOpcode() == Instruction::Add &&
 397              isa<CastInst>(I->getOperand(1))) {
 398
 399     if (PeepholeOptimizeAddCast(BB, BI, I->getOperand(0),
 400                                 cast<CastInst>(I->getOperand(1))))
 401       return true;
 402
 403 #endif
 404   }
 405
 406   return false;
 407 }
 408
 409
 410
 411
 412 static bool DoRaisePass(Method *M) {
 413   bool Changed = false;
 414   for (Method::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI) {
 415     BasicBlock *BB = *MI;
 416     BasicBlock::InstListType &BIL = BB->getInstList();
 417
 418     for (BasicBlock::iterator BI = BB->begin(); BI != BB->end();) {
 419       if (opt::DeadCodeElimination::dceInstruction(BIL, BI)) {
 420         Changed = true;
 421 #ifdef DEBUG_PEEPHOLE_INSTS
 422         cerr << "DeadCode Elinated!\n";
 423 #endif
 424       } else if (PeepholeOptimize(BB, BI))
 425         Changed = true;
 426       else
 427         ++BI;
 428     }
 429   }
 430   return Changed;
 431 }
 432
 433
 434
 435
 436 // DoInsertArrayCast - If the argument value has a pointer type, and if the
 437 // argument value is used as an array, insert a cast before the specified
 438 // basic block iterator that casts the value to an array pointer.  Return the
 439 // new cast instruction (in the CastResult var), or null if no cast is inserted.
 440 //
 441 static bool DoInsertArrayCast(Value *V, BasicBlock *BB,
 442                               BasicBlock::iterator InsertBefore) {
 443   const PointerType *ThePtrType = dyn_cast<PointerType>(V->getType());
 444   if (!ThePtrType) return false;
 445
 446   const Type *ElTy = ThePtrType->getValueType();
 447   if (isa<MethodType>(ElTy) || isa<ArrayType>(ElTy)) return false;
 448
 449   unsigned ElementSize = TD.getTypeSize(ElTy);
 450   bool InsertCast = false;
 451
 452   for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I) {
 453     Instruction *Inst = cast<Instruction>(*I);
 454     switch (Inst->getOpcode()) {
 455     case Instruction::Cast:          // There is already a cast instruction!
 456       if (const PointerType *PT = dyn_cast<const PointerType>(Inst->getType()))
 457         if (const ArrayType *AT = dyn_cast<const ArrayType>(PT->getValueType()))
 458           if (AT->getElementType() == ThePtrType->getValueType()) {
 459             // Cast already exists! Don't mess around with it.
 460             return false;       // No changes made to program though...
 461           }
 462       break;
 463     case Instruction::Add: {         // Analyze pointer arithmetic...
 464       Value *OtherOp = Inst->getOperand(Inst->getOperand(0) == V);
 465       analysis::ExprType Expr = analysis::ClassifyExpression(OtherOp);
 466
 467       // This looks like array addressing iff:
 468       //   A. The constant of the index is larger than the size of the element
 469       //      type.
 470       //   B. The scale factor is >= the size of the type.
 471       //
 472       if (Expr.Offset && getConstantValue(Expr.Offset) >= (int)ElementSize) // A
 473         InsertCast = true;
 474
 475       if (Expr.Scale && getConstantValue(Expr.Scale) >= (int)ElementSize) // B
 476         InsertCast = true;
 477
 478       break;
 479     }
 480     default: break;                  // Not an interesting use...
 481     }
 482   }
 483
 484   if (!InsertCast) return false;  // There is no reason to insert a cast!
 485
 486   // Calculate the destination pointer type
 487   const PointerType *DestTy = PointerType::get(ArrayType::get(ElTy));
 488
 489   // Check to make sure that all uses of the value can be converted over to use
 490   // the newly typed value.
 491   //
 492   ValueTypeCache ConvertedTypes;
 493   if (!ValueConvertableToType(V, DestTy, ConvertedTypes)) {
 494     cerr << "FAILED to convert types of values for " << V << "\n";
 495     ConvertedTypes.clear();
 496     ValueConvertableToType(V, DestTy, ConvertedTypes);
 497     return false;
 498   }
 499   ConvertedTypes.clear();
 500
 501   // Insert a cast!
 502   CastInst *TheCast =
 503     new CastInst(ConstPoolVal::getNullConstant(V->getType()), DestTy,
 504                  V->getName());
 505   BB->getInstList().insert(InsertBefore, TheCast);
 506
 507   cerr << "Inserting cast for " << V << endl;
 508
 509   // Convert users of the old value over to use the cast result...
 510   ValueMapCache VMC;
 511   ConvertValueToNewType(V, TheCast, VMC);
 512
 513   // The cast is the only thing that is allowed to reference the value...
 514   TheCast->setOperand(0, V);
 515
 516   cerr << "Inserted ptr-array cast: " << TheCast;
 517   return true;            // Made a change!
 518 }
 519
 520
 521 // DoInsertArrayCasts - Loop over all "incoming" values in the specified method,
 522 // inserting a cast for pointer values that are used as arrays. For our
 523 // purposes, an incoming value is considered to be either a value that is
 524 // either a method parameter, or a pointer returned from a function call.
 525 //
 526 static bool DoInsertArrayCasts(Method *M) {
 527   assert(!M->isExternal() && "Can't handle external methods!");
 528
 529   // Insert casts for all arguments to the function...
 530   bool Changed = false;
 531   BasicBlock *CurBB = M->front();
 532
 533   for (Method::ArgumentListType::iterator AI = M->getArgumentList().begin(),
 534          AE = M->getArgumentList().end(); AI != AE; ++AI) {
 535
 536     Changed |= DoInsertArrayCast(*AI, CurBB, CurBB->begin());
 537   }
 538
 539   // TODO: insert casts for alloca, malloc, and function call results.  Also,
 540   // look for pointers that already have casts, to add to the map.
 541
 542   return Changed;
 543 }
 544
 545
 546
 547
 548 // RaisePointerReferences::doit - Raise a method representation to a higher
 549 // level.
 550 //
 551 bool RaisePointerReferences::doit(Method *M) {
 552   if (M->isExternal()) return false;
 553
 554 #ifdef DEBUG_PEEPHOLE_INSTS
 555   cerr << "\n\n\nStarting to work on Method '" << M->getName() << "'\n";
 556 #endif
 557
 558   // Insert casts for all incoming pointer pointer values that are treated as
 559   // arrays...
 560   //
 561   bool Changed = false, LocalChange;
 562   do {
 563     LocalChange = DoInsertArrayCasts(M);
 564
 565     // Iterate over the method, refining it, until it converges on a stable
 566     // state
 567     while (DoRaisePass(M)) LocalChange = true;
 568     Changed |= LocalChange;
 569
 570   } while (LocalChange);
 571
 572   return Changed;
 573 }