contrib/llvm/lib/Analysis/LoopPass.cpp

   1 //===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements LoopPass and LPPassManager. All loop optimization
  11 // and transformation passes are derived from LoopPass. LPPassManager is
  12 // responsible for managing LoopPasses.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Analysis/LoopPass.h"
  17 #include "llvm/DebugInfoProbe.h"
  18 #include "llvm/Assembly/PrintModulePass.h"
  19 #include "llvm/Support/Debug.h"
  20 #include "llvm/Support/ManagedStatic.h"
  21 #include "llvm/Support/Timer.h"
  22 using namespace llvm;
  23
  24 namespace {
  25
  26 /// PrintLoopPass - Print a Function corresponding to a Loop.
  27 ///
  28 class PrintLoopPass : public LoopPass {
  29 private:
  30   std::string Banner;
  31   raw_ostream &Out;       // raw_ostream to print on.
  32
  33 public:
  34   static char ID;
  35   PrintLoopPass(const std::string &B, raw_ostream &o)
  36       : LoopPass(ID), Banner(B), Out(o) {}
  37
  38   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  39     AU.setPreservesAll();
  40   }
  41
  42   bool runOnLoop(Loop *L, LPPassManager &) {
  43     Out << Banner;
  44     for (Loop::block_iterator b = L->block_begin(), be = L->block_end();
  45          b != be;
  46          ++b) {
  47       (*b)->print(Out);
  48     }
  49     return false;
  50   }
  51 };
  52
  53 char PrintLoopPass::ID = 0;
  54 }
  55
  56 //===----------------------------------------------------------------------===//
  57 // DebugInfoProbe
  58
  59 static DebugInfoProbeInfo *TheDebugProbe;
  60 static void createDebugInfoProbe() {
  61   if (TheDebugProbe) return;
  62
  63   // Constructed the first time this is called. This guarantees that the
  64   // object will be constructed, if -enable-debug-info-probe is set,
  65   // before static globals, thus it will be destroyed before them.
  66   static ManagedStatic<DebugInfoProbeInfo> DIP;
  67   TheDebugProbe = &*DIP;
  68 }
  69
  70 //===----------------------------------------------------------------------===//
  71 // LPPassManager
  72 //
  73
  74 char LPPassManager::ID = 0;
  75
  76 LPPassManager::LPPassManager(int Depth)
  77   : FunctionPass(ID), PMDataManager(Depth) {
  78   skipThisLoop = false;
  79   redoThisLoop = false;
  80   LI = NULL;
  81   CurrentLoop = NULL;
  82 }
  83
  84 /// Delete loop from the loop queue and loop hierarchy (LoopInfo).
  85 void LPPassManager::deleteLoopFromQueue(Loop *L) {
  86
  87   if (Loop *ParentLoop = L->getParentLoop()) { // Not a top-level loop.
  88     // Reparent all of the blocks in this loop.  Since BBLoop had a parent,
  89     // they are now all in it.
  90     for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
  91          I != E; ++I)
  92       if (LI->getLoopFor(*I) == L)    // Don't change blocks in subloops.
  93         LI->changeLoopFor(*I, ParentLoop);
  94
  95     // Remove the loop from its parent loop.
  96     for (Loop::iterator I = ParentLoop->begin(), E = ParentLoop->end();;
  97          ++I) {
  98       assert(I != E && "Couldn't find loop");
  99       if (*I == L) {
 100         ParentLoop->removeChildLoop(I);
 101         break;
 102       }
 103     }
 104
 105     // Move all subloops into the parent loop.
 106     while (!L->empty())
 107       ParentLoop->addChildLoop(L->removeChildLoop(L->end()-1));
 108   } else {
 109     // Reparent all of the blocks in this loop.  Since BBLoop had no parent,
 110     // they no longer in a loop at all.
 111
 112     for (unsigned i = 0; i != L->getBlocks().size(); ++i) {
 113       // Don't change blocks in subloops.
 114       if (LI->getLoopFor(L->getBlocks()[i]) == L) {
 115         LI->removeBlock(L->getBlocks()[i]);
 116         --i;
 117       }
 118     }
 119
 120     // Remove the loop from the top-level LoopInfo object.
 121     for (LoopInfo::iterator I = LI->begin(), E = LI->end();; ++I) {
 122       assert(I != E && "Couldn't find loop");
 123       if (*I == L) {
 124         LI->removeLoop(I);
 125         break;
 126       }
 127     }
 128
 129     // Move all of the subloops to the top-level.
 130     while (!L->empty())
 131       LI->addTopLevelLoop(L->removeChildLoop(L->end()-1));
 132   }
 133
 134   delete L;
 135
 136   // If L is current loop then skip rest of the passes and let
 137   // runOnFunction remove L from LQ. Otherwise, remove L from LQ now
 138   // and continue applying other passes on CurrentLoop.
 139   if (CurrentLoop == L) {
 140     skipThisLoop = true;
 141     return;
 142   }
 143
 144   for (std::deque<Loop *>::iterator I = LQ.begin(),
 145          E = LQ.end(); I != E; ++I) {
 146     if (*I == L) {
 147       LQ.erase(I);
 148       break;
 149     }
 150   }
 151 }
 152
 153 // Inset loop into loop nest (LoopInfo) and loop queue (LQ).
 154 void LPPassManager::insertLoop(Loop *L, Loop *ParentLoop) {
 155
 156   assert (CurrentLoop != L && "Cannot insert CurrentLoop");
 157
 158   // Insert into loop nest
 159   if (ParentLoop)
 160     ParentLoop->addChildLoop(L);
 161   else
 162     LI->addTopLevelLoop(L);
 163
 164   insertLoopIntoQueue(L);
 165 }
 166
 167 void LPPassManager::insertLoopIntoQueue(Loop *L) {
 168   // Insert L into loop queue
 169   if (L == CurrentLoop)
 170     redoLoop(L);
 171   else if (!L->getParentLoop())
 172     // This is top level loop.
 173     LQ.push_front(L);
 174   else {
 175     // Insert L after the parent loop.
 176     for (std::deque<Loop *>::iterator I = LQ.begin(),
 177            E = LQ.end(); I != E; ++I) {
 178       if (*I == L->getParentLoop()) {
 179         // deque does not support insert after.
 180         ++I;
 181         LQ.insert(I, 1, L);
 182         break;
 183       }
 184     }
 185   }
 186 }
 187
 188 // Reoptimize this loop. LPPassManager will re-insert this loop into the
 189 // queue. This allows LoopPass to change loop nest for the loop. This
 190 // utility may send LPPassManager into infinite loops so use caution.
 191 void LPPassManager::redoLoop(Loop *L) {
 192   assert (CurrentLoop == L && "Can redo only CurrentLoop");
 193   redoThisLoop = true;
 194 }
 195
 196 /// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for
 197 /// all loop passes.
 198 void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From,
 199                                                   BasicBlock *To, Loop *L) {
 200   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 201     LoopPass *LP = getContainedPass(Index);
 202     LP->cloneBasicBlockAnalysis(From, To, L);
 203   }
 204 }
 205
 206 /// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes.
 207 void LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) {
 208   if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
 209     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;
 210          ++BI) {
 211       Instruction &I = *BI;
 212       deleteSimpleAnalysisValue(&I, L);
 213     }
 214   }
 215   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 216     LoopPass *LP = getContainedPass(Index);
 217     LP->deleteAnalysisValue(V, L);
 218   }
 219 }
 220
 221
 222 // Recurse through all subloops and all loops  into LQ.
 223 static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
 224   LQ.push_back(L);
 225   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 226     addLoopIntoQueue(*I, LQ);
 227 }
 228
 229 /// Pass Manager itself does not invalidate any analysis info.
 230 void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
 231   // LPPassManager needs LoopInfo. In the long term LoopInfo class will
 232   // become part of LPPassManager.
 233   Info.addRequired<LoopInfo>();
 234   Info.setPreservesAll();
 235 }
 236
 237 /// run - Execute all of the passes scheduled for execution.  Keep track of
 238 /// whether any of the passes modifies the function, and if so, return true.
 239 bool LPPassManager::runOnFunction(Function &F) {
 240   LI = &getAnalysis<LoopInfo>();
 241   bool Changed = false;
 242   createDebugInfoProbe();
 243
 244   // Collect inherited analysis from Module level pass manager.
 245   populateInheritedAnalysis(TPM->activeStack);
 246
 247   // Populate Loop Queue
 248   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
 249     addLoopIntoQueue(*I, LQ);
 250
 251   if (LQ.empty()) // No loops, skip calling finalizers
 252     return false;
 253
 254   // Initialization
 255   for (std::deque<Loop *>::const_iterator I = LQ.begin(), E = LQ.end();
 256        I != E; ++I) {
 257     Loop *L = *I;
 258     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 259       LoopPass *P = getContainedPass(Index);
 260       Changed |= P->doInitialization(L, *this);
 261     }
 262   }
 263
 264   // Walk Loops
 265   while (!LQ.empty()) {
 266
 267     CurrentLoop  = LQ.back();
 268     skipThisLoop = false;
 269     redoThisLoop = false;
 270
 271     // Run all passes on the current Loop.
 272     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 273       LoopPass *P = getContainedPass(Index);
 274       dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,
 275                    CurrentLoop->getHeader()->getName());
 276       dumpRequiredSet(P);
 277
 278       initializeAnalysisImpl(P);
 279       if (TheDebugProbe)
 280         TheDebugProbe->initialize(P, F);
 281       {
 282         PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
 283         TimeRegion PassTimer(getPassTimer(P));
 284
 285         Changed |= P->runOnLoop(CurrentLoop, *this);
 286       }
 287       if (TheDebugProbe)
 288         TheDebugProbe->finalize(P, F);
 289
 290       if (Changed)
 291         dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,
 292                      skipThisLoop ? "<deleted>" :
 293                                     CurrentLoop->getHeader()->getName());
 294       dumpPreservedSet(P);
 295
 296       if (!skipThisLoop) {
 297         // Manually check that this loop is still healthy. This is done
 298         // instead of relying on LoopInfo::verifyLoop since LoopInfo
 299         // is a function pass and it's really expensive to verify every
 300         // loop in the function every time. That level of checking can be
 301         // enabled with the -verify-loop-info option.
 302         {
 303           TimeRegion PassTimer(getPassTimer(LI));
 304           CurrentLoop->verifyLoop();
 305         }
 306
 307         // Then call the regular verifyAnalysis functions.
 308         verifyPreservedAnalysis(P);
 309       }
 310
 311       removeNotPreservedAnalysis(P);
 312       recordAvailableAnalysis(P);
 313       removeDeadPasses(P,
 314                        skipThisLoop ? "<deleted>" :
 315                                       CurrentLoop->getHeader()->getName(),
 316                        ON_LOOP_MSG);
 317
 318       if (skipThisLoop)
 319         // Do not run other passes on this loop.
 320         break;
 321     }
 322
 323     // If the loop was deleted, release all the loop passes. This frees up
 324     // some memory, and avoids trouble with the pass manager trying to call
 325     // verifyAnalysis on them.
 326     if (skipThisLoop)
 327       for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 328         Pass *P = getContainedPass(Index);
 329         freePass(P, "<deleted>", ON_LOOP_MSG);
 330       }
 331
 332     // Pop the loop from queue after running all passes.
 333     LQ.pop_back();
 334
 335     if (redoThisLoop)
 336       LQ.push_back(CurrentLoop);
 337   }
 338
 339   // Finalization
 340   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 341     LoopPass *P = getContainedPass(Index);
 342     Changed |= P->doFinalization();
 343   }
 344
 345   return Changed;
 346 }
 347
 348 /// Print passes managed by this manager
 349 void LPPassManager::dumpPassStructure(unsigned Offset) {
 350   errs().indent(Offset*2) << "Loop Pass Manager\n";
 351   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 352     Pass *P = getContainedPass(Index);
 353     P->dumpPassStructure(Offset + 1);
 354     dumpLastUses(P, Offset+1);
 355   }
 356 }
 357
 358
 359 //===----------------------------------------------------------------------===//
 360 // LoopPass
 361
 362 Pass *LoopPass::createPrinterPass(raw_ostream &O,
 363                                   const std::string &Banner) const {
 364   return new PrintLoopPass(Banner, O);
 365 }
 366
 367 // Check if this pass is suitable for the current LPPassManager, if
 368 // available. This pass P is not suitable for a LPPassManager if P
 369 // is not preserving higher level analysis info used by other
 370 // LPPassManager passes. In such case, pop LPPassManager from the
 371 // stack. This will force assignPassManager() to create new
 372 // LPPassManger as expected.
 373 void LoopPass::preparePassManager(PMStack &PMS) {
 374
 375   // Find LPPassManager
 376   while (!PMS.empty() &&
 377          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
 378     PMS.pop();
 379
 380   // If this pass is destroying high level information that is used
 381   // by other passes that are managed by LPM then do not insert
 382   // this pass in current LPM. Use new LPPassManager.
 383   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager &&
 384       !PMS.top()->preserveHigherLevelAnalysis(this))
 385     PMS.pop();
 386 }
 387
 388 /// Assign pass manager to manage this pass.
 389 void LoopPass::assignPassManager(PMStack &PMS,
 390                                  PassManagerType PreferredType) {
 391   // Find LPPassManager
 392   while (!PMS.empty() &&
 393          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
 394     PMS.pop();
 395
 396   LPPassManager *LPPM;
 397   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager)
 398     LPPM = (LPPassManager*)PMS.top();
 399   else {
 400     // Create new Loop Pass Manager if it does not exist.
 401     assert (!PMS.empty() && "Unable to create Loop Pass Manager");
 402     PMDataManager *PMD = PMS.top();
 403
 404     // [1] Create new Call Graph Pass Manager
 405     LPPM = new LPPassManager(PMD->getDepth() + 1);
 406     LPPM->populateInheritedAnalysis(PMS);
 407
 408     // [2] Set up new manager's top level manager
 409     PMTopLevelManager *TPM = PMD->getTopLevelManager();
 410     TPM->addIndirectPassManager(LPPM);
 411
 412     // [3] Assign manager to manage this new manager. This may create
 413     // and push new managers into PMS
 414     Pass *P = LPPM->getAsPass();
 415     TPM->schedulePass(P);
 416
 417     // [4] Push new manager into PMS
 418     PMS.push(LPPM);
 419   }
 420
 421   LPPM->add(this);
 422 }