From 30159729ad3f8dcd6615d5e8a049e5e3e93be423 Mon Sep 17 00:00:00 2001
From: Devang Patel <dpatel@apple.com>
Date: Tue, 6 Mar 2007 02:30:46 +0000
Subject: [PATCH] Use std::deque to manage loop queue inside LPPassManager.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34943 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/Analysis/LoopPass.h |  4 +--
 lib/Analysis/LoopPass.cpp        | 46 +++++---------------------------
 2 files changed, 7 insertions(+), 43 deletions(-)

diff --git a/include/llvm/Analysis/LoopPass.h b/include/llvm/Analysis/LoopPass.h
index a231598417c..cf5611beb5f 100644
--- a/include/llvm/Analysis/LoopPass.h
+++ b/include/llvm/Analysis/LoopPass.h
@@ -25,7 +25,6 @@ namespace llvm {
 class LPPassManager;
 class Loop;
 class Function;
-class LoopQueue;
 
 class LoopPass : public Pass {
 
@@ -47,7 +46,6 @@ class LPPassManager : public FunctionPass, public PMDataManager {
 
 public:
   LPPassManager(int Depth);
-  ~LPPassManager();
 
   /// run - Execute all of the passes scheduled for execution.  Keep track of
   /// whether any of the passes modifies the module, and if so, return true.
@@ -95,7 +93,7 @@ public:
   // utility may send LPPassManager into infinite loops so use caution.
   void redoLoop(Loop *L);
 private:
-  LoopQueue *LQ;
+  std::deque<Loop *> LQ;
   bool skipThisLoop;
   bool redoThisLoop;
 };
diff --git a/lib/Analysis/LoopPass.cpp b/lib/Analysis/LoopPass.cpp
index 40b38f37930..fe1672a4037 100644
--- a/lib/Analysis/LoopPass.cpp
+++ b/lib/Analysis/LoopPass.cpp
@@ -14,37 +14,8 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LoopPass.h"
-#include <queue>
 using namespace llvm;
 
-//===----------------------------------------------------------------------===//
-// LoopQueue
-
-namespace llvm {
-
-// Compare Two loops based on their depth in loop nest.
-class LoopCompare {
-public:
-  bool operator()( Loop *L1, Loop *L2) const {
-    // Loops with highest depth has the highest priority.
-    return L1->getLoopDepth() < L2->getLoopDepth();
-  }
-};
-
-// Loop queue used by Loop Pass Manager. This is a wrapper class
-// that hides implemenation detail (use of priority_queue) inside .cpp file.
-class LoopQueue {
-public:
-  inline void push(Loop *L) { LPQ.push(L); }
-  inline void pop() { LPQ.pop(); }
-  inline Loop *top() { return LPQ.top(); }
-  inline bool empty() { return LPQ.empty(); }
-private:
-  std::priority_queue<Loop *, std::vector<Loop *>, LoopCompare> LPQ;
-};
-
-} // End of LLVM namespace
-
 //===----------------------------------------------------------------------===//
 // LPPassManager
 //
@@ -53,11 +24,6 @@ private:
 LPPassManager::LPPassManager(int Depth) : PMDataManager(Depth) { 
   skipThisLoop = false;
   redoThisLoop = false;
-  LQ = new LoopQueue(); 
-}
-
-LPPassManager::~LPPassManager() {
-  delete LQ;
 }
 
 /// Delete loop from the loop queue. This is used by Loop pass to inform
@@ -75,10 +41,10 @@ void LPPassManager::redoLoop(Loop *L) {
 }
 
 // Recurse through all subloops and all loops  into LQ.
-static void addLoopIntoQueue(Loop *L, LoopQueue *LQ) {
+static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
     addLoopIntoQueue(*I, LQ);
-  LQ->push(L);
+  LQ.push_back(L);
 }
 
 /// run - Execute all of the passes scheduled for execution.  Keep track of
@@ -92,9 +58,9 @@ bool LPPassManager::runOnFunction(Function &F) {
     addLoopIntoQueue(*I, LQ);
 
   // Walk Loops
-  while (!LQ->empty()) {
+  while (!LQ.empty()) {
       
-    Loop *L  = LQ->top();
+    Loop *L  = LQ.back();
     skipThisLoop = false;
     redoThisLoop = false;
 
@@ -130,10 +96,10 @@ bool LPPassManager::runOnFunction(Function &F) {
     }
     
     // Pop the loop from queue after running all passes.
-    LQ->pop();
+    LQ.pop_back();
     
     if (redoThisLoop)
-      LQ->push(L);
+      LQ.push_back(L);
   }
 
   return Changed;
-- 
2.34.1