[rustc.git] / src / llvm / lib / Analysis / LoopPass.cpp

//===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements LoopPass and LPPassManager. All loop optimization
// and transformation passes are derived from LoopPass. LPPassManager is
// responsible for managing LoopPasses.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/LoopPass.h"
#include "llvm/IR/IRPrintingPasses.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Timer.h"
using namespace llvm;

#define DEBUG_TYPE "loop-pass-manager"

namespace {

/// PrintLoopPass - Print a Function corresponding to a Loop.
///
class PrintLoopPass : public LoopPass {
private:
  std::string Banner;
  raw_ostream &Out;       // raw_ostream to print on.

public:
  static char ID;
  PrintLoopPass(const std::string &B, raw_ostream &o)
      : LoopPass(ID), Banner(B), Out(o) {}

  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.setPreservesAll();
  }

  bool runOnLoop(Loop *L, LPPassManager &) override {
    Out << Banner;
    for (Loop::block_iterator b = L->block_begin(), be = L->block_end();
         b != be;
         ++b) {
      if (*b)
        (*b)->print(Out);
      else
        Out << "Printing <null> block";
    }
    return false;
  }
};

char PrintLoopPass::ID = 0;
}

//===----------------------------------------------------------------------===//
// LPPassManager
//

char LPPassManager::ID = 0;

LPPassManager::LPPassManager()
  : FunctionPass(ID), PMDataManager() {
  skipThisLoop = false;
  redoThisLoop = false;
  LI = nullptr;
  CurrentLoop = nullptr;
}

/// Delete loop from the loop queue and loop hierarchy (LoopInfo).
void LPPassManager::deleteLoopFromQueue(Loop *L) {

  LI->updateUnloop(L);

  // Notify passes that the loop is being deleted.
  deleteSimpleAnalysisLoop(L);

  // If L is current loop then skip rest of the passes and let
  // runOnFunction remove L from LQ. Otherwise, remove L from LQ now
  // and continue applying other passes on CurrentLoop.
  if (CurrentLoop == L)
    skipThisLoop = true;

  delete L;

  if (skipThisLoop)
    return;

  for (std::deque<Loop *>::iterator I = LQ.begin(),
         E = LQ.end(); I != E; ++I) {
    if (*I == L) {
      LQ.erase(I);
      break;
    }
  }
}

// Inset loop into loop nest (LoopInfo) and loop queue (LQ).
void LPPassManager::insertLoop(Loop *L, Loop *ParentLoop) {

  assert (CurrentLoop != L && "Cannot insert CurrentLoop");

  // Insert into loop nest
  if (ParentLoop)
    ParentLoop->addChildLoop(L);
  else
    LI->addTopLevelLoop(L);

  insertLoopIntoQueue(L);
}

void LPPassManager::insertLoopIntoQueue(Loop *L) {
  // Insert L into loop queue
  if (L == CurrentLoop)
    redoLoop(L);
  else if (!L->getParentLoop())
    // This is top level loop.
    LQ.push_front(L);
  else {
    // Insert L after the parent loop.
    for (std::deque<Loop *>::iterator I = LQ.begin(),
           E = LQ.end(); I != E; ++I) {
      if (*I == L->getParentLoop()) {
        // deque does not support insert after.
        ++I;
        LQ.insert(I, 1, L);
        break;
      }
    }
  }
}

// Reoptimize this loop. LPPassManager will re-insert this loop into the
// queue. This allows LoopPass to change loop nest for the loop. This
// utility may send LPPassManager into infinite loops so use caution.
void LPPassManager::redoLoop(Loop *L) {
  assert (CurrentLoop == L && "Can redo only CurrentLoop");
  redoThisLoop = true;
}

/// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for
/// all loop passes.
void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From,
                                                  BasicBlock *To, Loop *L) {
  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    LoopPass *LP = getContainedPass(Index);
    LP->cloneBasicBlockAnalysis(From, To, L);
  }
}

/// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes.
void LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) {
  if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
    for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;
         ++BI) {
      Instruction &I = *BI;
      deleteSimpleAnalysisValue(&I, L);
    }
  }
  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    LoopPass *LP = getContainedPass(Index);
    LP->deleteAnalysisValue(V, L);
  }
}

/// Invoke deleteAnalysisLoop hook for all passes.
void LPPassManager::deleteSimpleAnalysisLoop(Loop *L) {
  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    LoopPass *LP = getContainedPass(Index);
    LP->deleteAnalysisLoop(L);
  }
}


// Recurse through all subloops and all loops  into LQ.
static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
  LQ.push_back(L);
  for (Loop::reverse_iterator I = L->rbegin(), E = L->rend(); I != E; ++I)
    addLoopIntoQueue(*I, LQ);
}

/// Pass Manager itself does not invalidate any analysis info.
void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
  // LPPassManager needs LoopInfo. In the long term LoopInfo class will
  // become part of LPPassManager.
  Info.addRequired<LoopInfo>();
  Info.setPreservesAll();
}

/// run - Execute all of the passes scheduled for execution.  Keep track of
/// whether any of the passes modifies the function, and if so, return true.
bool LPPassManager::runOnFunction(Function &F) {
  LI = &getAnalysis<LoopInfo>();
  bool Changed = false;

  // Collect inherited analysis from Module level pass manager.
  populateInheritedAnalysis(TPM->activeStack);

  // Populate the loop queue in reverse program order. There is no clear need to
  // process sibling loops in either forward or reverse order. There may be some
  // advantage in deleting uses in a later loop before optimizing the
  // definitions in an earlier loop. If we find a clear reason to process in
  // forward order, then a forward variant of LoopPassManager should be created.
  //
  // Note that LoopInfo::iterator visits loops in reverse program
  // order. Here, reverse_iterator gives us a forward order, and the LoopQueue
  // reverses the order a third time by popping from the back.
  for (LoopInfo::reverse_iterator I = LI->rbegin(), E = LI->rend(); I != E; ++I)
    addLoopIntoQueue(*I, LQ);

  if (LQ.empty()) // No loops, skip calling finalizers
    return false;

  // Initialization
  for (std::deque<Loop *>::const_iterator I = LQ.begin(), E = LQ.end();
       I != E; ++I) {
    Loop *L = *I;
    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
      LoopPass *P = getContainedPass(Index);
      Changed |= P->doInitialization(L, *this);
    }
  }

  // Walk Loops
  while (!LQ.empty()) {

    CurrentLoop  = LQ.back();
    skipThisLoop = false;
    redoThisLoop = false;

    // Run all passes on the current Loop.
    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
      LoopPass *P = getContainedPass(Index);

      dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,
                   CurrentLoop->getHeader()->getName());
      dumpRequiredSet(P);

      initializeAnalysisImpl(P);

      {
        PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
        TimeRegion PassTimer(getPassTimer(P));

        Changed |= P->runOnLoop(CurrentLoop, *this);
      }

      if (Changed)
        dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,
                     skipThisLoop ? "<deleted>" :
                                    CurrentLoop->getHeader()->getName());
      dumpPreservedSet(P);

      if (!skipThisLoop) {
        // Manually check that this loop is still healthy. This is done
        // instead of relying on LoopInfo::verifyLoop since LoopInfo
        // is a function pass and it's really expensive to verify every
        // loop in the function every time. That level of checking can be
        // enabled with the -verify-loop-info option.
        {
          TimeRegion PassTimer(getPassTimer(LI));
          CurrentLoop->verifyLoop();
        }

        // Then call the regular verifyAnalysis functions.
        verifyPreservedAnalysis(P);

        F.getContext().yield();
      }

      removeNotPreservedAnalysis(P);
      recordAvailableAnalysis(P);
      removeDeadPasses(P,
                       skipThisLoop ? "<deleted>" :
                                      CurrentLoop->getHeader()->getName(),
                       ON_LOOP_MSG);

      if (skipThisLoop)
        // Do not run other passes on this loop.
        break;
    }

    // If the loop was deleted, release all the loop passes. This frees up
    // some memory, and avoids trouble with the pass manager trying to call
    // verifyAnalysis on them.
    if (skipThisLoop)
      for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
        Pass *P = getContainedPass(Index);
        freePass(P, "<deleted>", ON_LOOP_MSG);
      }

    // Pop the loop from queue after running all passes.
    LQ.pop_back();

    if (redoThisLoop)
      LQ.push_back(CurrentLoop);
  }

  // Finalization
  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    LoopPass *P = getContainedPass(Index);
    Changed |= P->doFinalization();
  }

  return Changed;
}

/// Print passes managed by this manager
void LPPassManager::dumpPassStructure(unsigned Offset) {
  errs().indent(Offset*2) << "Loop Pass Manager\n";
  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    Pass *P = getContainedPass(Index);
    P->dumpPassStructure(Offset + 1);
    dumpLastUses(P, Offset+1);
  }
}


//===----------------------------------------------------------------------===//
// LoopPass

Pass *LoopPass::createPrinterPass(raw_ostream &O,
                                  const std::string &Banner) const {
  return new PrintLoopPass(Banner, O);
}

// Check if this pass is suitable for the current LPPassManager, if
// available. This pass P is not suitable for a LPPassManager if P
// is not preserving higher level analysis info used by other
// LPPassManager passes. In such case, pop LPPassManager from the
// stack. This will force assignPassManager() to create new
// LPPassManger as expected.
void LoopPass::preparePassManager(PMStack &PMS) {

  // Find LPPassManager
  while (!PMS.empty() &&
         PMS.top()->getPassManagerType() > PMT_LoopPassManager)
    PMS.pop();

  // If this pass is destroying high level information that is used
  // by other passes that are managed by LPM then do not insert
  // this pass in current LPM. Use new LPPassManager.
  if (PMS.top()->getPassManagerType() == PMT_LoopPassManager &&
      !PMS.top()->preserveHigherLevelAnalysis(this))
    PMS.pop();
}

/// Assign pass manager to manage this pass.
void LoopPass::assignPassManager(PMStack &PMS,
                                 PassManagerType PreferredType) {
  // Find LPPassManager
  while (!PMS.empty() &&
         PMS.top()->getPassManagerType() > PMT_LoopPassManager)
    PMS.pop();

  LPPassManager *LPPM;
  if (PMS.top()->getPassManagerType() == PMT_LoopPassManager)
    LPPM = (LPPassManager*)PMS.top();
  else {
    // Create new Loop Pass Manager if it does not exist.
    assert (!PMS.empty() && "Unable to create Loop Pass Manager");
    PMDataManager *PMD = PMS.top();

    // [1] Create new Loop Pass Manager
    LPPM = new LPPassManager();
    LPPM->populateInheritedAnalysis(PMS);

    // [2] Set up new manager's top level manager
    PMTopLevelManager *TPM = PMD->getTopLevelManager();
    TPM->addIndirectPassManager(LPPM);

    // [3] Assign manager to manage this new manager. This may create
    // and push new managers into PMS
    Pass *P = LPPM->getAsPass();
    TPM->schedulePass(P);

    // [4] Push new manager into PMS
    PMS.push(LPPM);
  }

  LPPM->add(this);
}

// Containing function has Attribute::OptimizeNone and transformation
// passes should skip it.
bool LoopPass::skipOptnoneFunction(const Loop *L) const {
  const Function *F = L->getHeader()->getParent();
  if (F && F->hasFnAttribute(Attribute::OptimizeNone)) {
    // FIXME: Report this to dbgs() only once per function.
    DEBUG(dbgs() << "Skipping pass '" << getPassName()
          << "' in function " << F->getName() << "\n");
    // FIXME: Delete loop from pass manager's queue?
    return true;
  }
  return false;
}
Commit	Line	Data
223e47cc LB	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"
1a4d82fc JJ	17	#include "llvm/IR/IRPrintingPasses.h"
1a4d82fc JJ	18	#include "llvm/IR/LLVMContext.h"
223e47cc LB	19	#include "llvm/Support/Debug.h"
	20	#include "llvm/Support/Timer.h"
	21	using namespace llvm;
	22
1a4d82fc JJ	23	#define DEBUG_TYPE "loop-pass-manager"
1a4d82fc JJ	24
223e47cc LB	25	namespace {
	26
	27	/// PrintLoopPass - Print a Function corresponding to a Loop.
	28	///
	29	class PrintLoopPass : public LoopPass {
	30	private:
	31	std::string Banner;
	32	raw_ostream &Out; // raw_ostream to print on.
	33
	34	public:
	35	static char ID;
	36	PrintLoopPass(const std::string &B, raw_ostream &o)
	37	: LoopPass(ID), Banner(B), Out(o) {}
	38
1a4d82fc	39	void getAnalysisUsage(AnalysisUsage &AU) const override {
223e47cc LB	40	AU.setPreservesAll();
	41	}
	42
1a4d82fc	43	bool runOnLoop(Loop *L, LPPassManager &) override {
223e47cc LB	44	Out << Banner;
	45	for (Loop::block_iterator b = L->block_begin(), be = L->block_end();
	46	b != be;
	47	++b) {
1a4d82fc JJ	48	if (*b)
	49	(*b)->print(Out);
	50	else
	51	Out << "Printing <null> block";
223e47cc LB	52	}
	53	return false;
	54	}
	55	};
	56
	57	char PrintLoopPass::ID = 0;
	58	}
	59
	60	//===----------------------------------------------------------------------===//
	61	// LPPassManager
	62	//
	63
	64	char LPPassManager::ID = 0;
	65
	66	LPPassManager::LPPassManager()
	67	: FunctionPass(ID), PMDataManager() {
	68	skipThisLoop = false;
	69	redoThisLoop = false;
1a4d82fc JJ	70	LI = nullptr;
1a4d82fc JJ	71	CurrentLoop = nullptr;
223e47cc LB	72	}
	73
	74	/// Delete loop from the loop queue and loop hierarchy (LoopInfo).
	75	void LPPassManager::deleteLoopFromQueue(Loop *L) {
	76
	77	LI->updateUnloop(L);
	78
1a4d82fc JJ	79	// Notify passes that the loop is being deleted.
	80	deleteSimpleAnalysisLoop(L);
	81
223e47cc LB	82	// If L is current loop then skip rest of the passes and let
	83	// runOnFunction remove L from LQ. Otherwise, remove L from LQ now
	84	// and continue applying other passes on CurrentLoop.
	85	if (CurrentLoop == L)
	86	skipThisLoop = true;
	87
	88	delete L;
	89
	90	if (skipThisLoop)
	91	return;
	92
	93	for (std::deque<Loop *>::iterator I = LQ.begin(),
	94	E = LQ.end(); I != E; ++I) {
	95	if (*I == L) {
	96	LQ.erase(I);
	97	break;
	98	}
	99	}
	100	}
	101
	102	// Inset loop into loop nest (LoopInfo) and loop queue (LQ).
	103	void LPPassManager::insertLoop(Loop L, Loop ParentLoop) {
	104
	105	assert (CurrentLoop != L && "Cannot insert CurrentLoop");
	106
	107	// Insert into loop nest
	108	if (ParentLoop)
	109	ParentLoop->addChildLoop(L);
	110	else
	111	LI->addTopLevelLoop(L);
	112
	113	insertLoopIntoQueue(L);
	114	}
	115
	116	void LPPassManager::insertLoopIntoQueue(Loop *L) {
	117	// Insert L into loop queue
	118	if (L == CurrentLoop)
	119	redoLoop(L);
	120	else if (!L->getParentLoop())
	121	// This is top level loop.
	122	LQ.push_front(L);
	123	else {
	124	// Insert L after the parent loop.
	125	for (std::deque<Loop *>::iterator I = LQ.begin(),
	126	E = LQ.end(); I != E; ++I) {
	127	if (*I == L->getParentLoop()) {
	128	// deque does not support insert after.
	129	++I;
	130	LQ.insert(I, 1, L);
	131	break;
	132	}
	133	}
	134	}
	135	}
	136
	137	// Reoptimize this loop. LPPassManager will re-insert this loop into the
	138	// queue. This allows LoopPass to change loop nest for the loop. This
	139	// utility may send LPPassManager into infinite loops so use caution.
	140	void LPPassManager::redoLoop(Loop *L) {
	141	assert (CurrentLoop == L && "Can redo only CurrentLoop");
	142	redoThisLoop = true;
	143	}
	144
	145	/// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for
146	/// all loop passes.
147	void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From,
148	BasicBlock To, Loop L) {
149	for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
150	LoopPass *LP = getContainedPass(Index);
151	LP->cloneBasicBlockAnalysis(From, To, L);
152	}
153	}
154
155	/// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes.
156	void LPPassManager::deleteSimpleAnalysisValue(Value V, Loop L) {
157	if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
158	for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;
159	++BI) {
160	Instruction &I = *BI;
161	deleteSimpleAnalysisValue(&I, L);
162	}
163	}
164	for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
165	LoopPass *LP = getContainedPass(Index);
166	LP->deleteAnalysisValue(V, L);
167	}
168	}
169
1a4d82fc JJ	170	/// Invoke deleteAnalysisLoop hook for all passes.
	171	void LPPassManager::deleteSimpleAnalysisLoop(Loop *L) {
	172	for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
	173	LoopPass *LP = getContainedPass(Index);
	174	LP->deleteAnalysisLoop(L);
	175	}
	176	}
	177
223e47cc LB	178
	179	// Recurse through all subloops and all loops into LQ.
	180	static void addLoopIntoQueue(Loop L, std::deque<Loop > &LQ) {
	181	LQ.push_back(L);
	182	for (Loop::reverse_iterator I = L->rbegin(), E = L->rend(); I != E; ++I)
	183	addLoopIntoQueue(*I, LQ);
	184	}
	185
	186	/// Pass Manager itself does not invalidate any analysis info.
	187	void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
	188	// LPPassManager needs LoopInfo. In the long term LoopInfo class will
	189	// become part of LPPassManager.
	190	Info.addRequired<LoopInfo>();
	191	Info.setPreservesAll();
	192	}
	193
	194	/// run - Execute all of the passes scheduled for execution. Keep track of
	195	/// whether any of the passes modifies the function, and if so, return true.
	196	bool LPPassManager::runOnFunction(Function &F) {
	197	LI = &getAnalysis<LoopInfo>();
	198	bool Changed = false;
	199
	200	// Collect inherited analysis from Module level pass manager.
	201	populateInheritedAnalysis(TPM->activeStack);
	202
	203	// Populate the loop queue in reverse program order. There is no clear need to
	204	// process sibling loops in either forward or reverse order. There may be some
	205	// advantage in deleting uses in a later loop before optimizing the
	206	// definitions in an earlier loop. If we find a clear reason to process in
	207	// forward order, then a forward variant of LoopPassManager should be created.
1a4d82fc JJ	208	//
	209	// Note that LoopInfo::iterator visits loops in reverse program
	210	// order. Here, reverse_iterator gives us a forward order, and the LoopQueue
	211	// reverses the order a third time by popping from the back.
223e47cc LB	212	for (LoopInfo::reverse_iterator I = LI->rbegin(), E = LI->rend(); I != E; ++I)
	213	addLoopIntoQueue(*I, LQ);
	214
	215	if (LQ.empty()) // No loops, skip calling finalizers
	216	return false;
	217
	218	// Initialization
	219	for (std::deque<Loop *>::const_iterator I = LQ.begin(), E = LQ.end();
	220	I != E; ++I) {
	221	Loop L = I;
	222	for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
	223	LoopPass *P = getContainedPass(Index);
	224	Changed \|= P->doInitialization(L, *this);
	225	}
	226	}
	227
	228	// Walk Loops
	229	while (!LQ.empty()) {
	230
	231	CurrentLoop = LQ.back();
	232	skipThisLoop = false;
	233	redoThisLoop = false;
	234
	235	// Run all passes on the current Loop.
	236	for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
	237	LoopPass *P = getContainedPass(Index);
	238
	239	dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,
	240	CurrentLoop->getHeader()->getName());
	241	dumpRequiredSet(P);
	242
	243	initializeAnalysisImpl(P);
	244
	245	{
	246	PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
	247	TimeRegion PassTimer(getPassTimer(P));
	248
	249	Changed \|= P->runOnLoop(CurrentLoop, *this);
	250	}
	251
	252	if (Changed)
	253	dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,
	254	skipThisLoop ? "<deleted>" :
	255	CurrentLoop->getHeader()->getName());
	256	dumpPreservedSet(P);
	257
	258	if (!skipThisLoop) {
	259	// Manually check that this loop is still healthy. This is done
	260	// instead of relying on LoopInfo::verifyLoop since LoopInfo
	261	// is a function pass and it's really expensive to verify every
	262	// loop in the function every time. That level of checking can be
	263	// enabled with the -verify-loop-info option.
	264	{
	265	TimeRegion PassTimer(getPassTimer(LI));
	266	CurrentLoop->verifyLoop();
	267	}
	268
	269	// Then call the regular verifyAnalysis functions.
	270	verifyPreservedAnalysis(P);
1a4d82fc JJ	271
1a4d82fc JJ	272	F.getContext().yield();
223e47cc LB	273	}
	274
	275	removeNotPreservedAnalysis(P);
	276	recordAvailableAnalysis(P);
	277	removeDeadPasses(P,
	278	skipThisLoop ? "<deleted>" :
	279	CurrentLoop->getHeader()->getName(),
	280	ON_LOOP_MSG);
	281
	282	if (skipThisLoop)
	283	// Do not run other passes on this loop.
	284	break;
	285	}
	286
	287	// If the loop was deleted, release all the loop passes. This frees up
	288	// some memory, and avoids trouble with the pass manager trying to call
	289	// verifyAnalysis on them.
	290	if (skipThisLoop)
	291	for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
	292	Pass *P = getContainedPass(Index);
	293	freePass(P, "<deleted>", ON_LOOP_MSG);
	294	}
	295
	296	// Pop the loop from queue after running all passes.
	297	LQ.pop_back();
	298
	299	if (redoThisLoop)
	300	LQ.push_back(CurrentLoop);
	301	}
	302
	303	// Finalization
	304	for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
	305	LoopPass *P = getContainedPass(Index);
	306	Changed \|= P->doFinalization();
	307	}
	308
	309	return Changed;
	310	}
	311
	312	/// Print passes managed by this manager
	313	void LPPassManager::dumpPassStructure(unsigned Offset) {
	314	errs().indent(Offset*2) << "Loop Pass Manager\n";
	315	for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
	316	Pass *P = getContainedPass(Index);
	317	P->dumpPassStructure(Offset + 1);
	318	dumpLastUses(P, Offset+1);
	319	}
	320	}
	321
	322
	323	//===----------------------------------------------------------------------===//
	324	// LoopPass
	325
	326	Pass *LoopPass::createPrinterPass(raw_ostream &O,
	327	const std::string &Banner) const {
	328	return new PrintLoopPass(Banner, O);
	329	}
	330
	331	// Check if this pass is suitable for the current LPPassManager, if
	332	// available. This pass P is not suitable for a LPPassManager if P
	333	// is not preserving higher level analysis info used by other
	334	// LPPassManager passes. In such case, pop LPPassManager from the
	335	// stack. This will force assignPassManager() to create new
	336	// LPPassManger as expected.
337	void LoopPass::preparePassManager(PMStack &PMS) {
338
339	// Find LPPassManager
340	while (!PMS.empty() &&
341	PMS.top()->getPassManagerType() > PMT_LoopPassManager)
342	PMS.pop();
343
344	// If this pass is destroying high level information that is used
345	// by other passes that are managed by LPM then do not insert
346	// this pass in current LPM. Use new LPPassManager.
347	if (PMS.top()->getPassManagerType() == PMT_LoopPassManager &&
348	!PMS.top()->preserveHigherLevelAnalysis(this))
349	PMS.pop();
350	}
351
352	/// Assign pass manager to manage this pass.
353	void LoopPass::assignPassManager(PMStack &PMS,
354	PassManagerType PreferredType) {
355	// Find LPPassManager
356	while (!PMS.empty() &&
357	PMS.top()->getPassManagerType() > PMT_LoopPassManager)
358	PMS.pop();
359
360	LPPassManager *LPPM;
361	if (PMS.top()->getPassManagerType() == PMT_LoopPassManager)
362	LPPM = (LPPassManager*)PMS.top();
363	else {
364	// Create new Loop Pass Manager if it does not exist.
365	assert (!PMS.empty() && "Unable to create Loop Pass Manager");
366	PMDataManager *PMD = PMS.top();
367
368	// [1] Create new Loop Pass Manager
369	LPPM = new LPPassManager();
370	LPPM->populateInheritedAnalysis(PMS);
371
372	// [2] Set up new manager's top level manager
373	PMTopLevelManager *TPM = PMD->getTopLevelManager();
374	TPM->addIndirectPassManager(LPPM);
375
376	// [3] Assign manager to manage this new manager. This may create
377	// and push new managers into PMS
378	Pass *P = LPPM->getAsPass();
379	TPM->schedulePass(P);
380
381	// [4] Push new manager into PMS
382	PMS.push(LPPM);
383	}
384
385	LPPM->add(this);
386	}
1a4d82fc JJ	387
	388	// Containing function has Attribute::OptimizeNone and transformation
	389	// passes should skip it.
	390	bool LoopPass::skipOptnoneFunction(const Loop *L) const {
	391	const Function *F = L->getHeader()->getParent();
	392	if (F && F->hasFnAttribute(Attribute::OptimizeNone)) {
	393	// FIXME: Report this to dbgs() only once per function.
	394	DEBUG(dbgs() << "Skipping pass '" << getPassName()
	395	<< "' in function " << F->getName() << "\n");
	396	// FIXME: Delete loop from pass manager's queue?
	397	return true;
	398	}
	399	return false;
	400	}