X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FInterval.cpp;h=404d2c2f4a88c423c316c79ad190f169c976314f;hb=663e711dc235cae94eb50abb1c0571fd0b3a6a35;hp=f1737fc39af106f46a7eb83e1e3f952b76b632b0;hpb=2275c1d55d48a48d23089e8ce18bab275eaebac8;p=oota-llvm.git

diff --git a/lib/Analysis/Interval.cpp b/lib/Analysis/Interval.cpp
index f1737fc39af..404d2c2f4a8 100644
--- a/lib/Analysis/Interval.cpp
+++ b/lib/Analysis/Interval.cpp
@@ -1,85 +1,57 @@
-//===- Intervals.cpp - Interval partition Calculation ------------*- C++ -*--=//
+//===- Interval.cpp - Interval class code ---------------------------------===//
 //
-// This file contains the declaration of the cfg::IntervalPartition class, which
-// calculates and represent the interval partition of a method.
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains the definition of the Interval class, which represents a
+// partition of a control flow graph of some kind.
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Analysis/Intervals.h"
-#include "llvm/Method.h"
+#include "llvm/Analysis/Interval.h"
 #include "llvm/BasicBlock.h"
-#include "llvm/CFG.h"
+#include "llvm/Support/CFG.h"
+#include <algorithm>
 
-void cfg::IntervalPartition::UpdateSuccessors(cfg::Interval *Int) {
-  BasicBlock *Header = Int->HeaderNode;
-  for (cfg::Interval::succ_iterator I = Int->Successors.begin(), 
-	                            E = Int->Successors.end(); I != E; ++I)
-    getBlockInterval(*I)->Predecessors.push_back(Header);
-}
-
-// IntervalPartition ctor - Build the partition for the specified method
-cfg::IntervalPartition::IntervalPartition(Method *M) {
-  BasicBlock *MethodStart = M->getBasicBlocks().front();
-  assert(MethodStart && "Cannot operate on prototypes!");
+using namespace llvm;
 
-  ProcessInterval(MethodStart);
-  RootInterval = getBlockInterval(MethodStart);
+//===----------------------------------------------------------------------===//
+// Interval Implementation
+//===----------------------------------------------------------------------===//
 
-  // Now that we know all of the successor information, propogate this to the
-  // predecessors for each block...
-  for(iterator I = begin(), E = end(); I != E; ++I)
-    UpdateSuccessors(*I);
+// isLoop - Find out if there is a back edge in this interval...
+//
+bool Interval::isLoop() const {
+  // There is a loop in this interval iff one of the predecessors of the header
+  // node lives in the interval.
+  for (::pred_iterator I = ::pred_begin(HeaderNode), E = ::pred_end(HeaderNode);
+       I != E; ++I) {
+    if (contains(*I)) return true;
+  }
+  return false;
 }
 
-void cfg::IntervalPartition::ProcessInterval(BasicBlock *Header) {
-  if (getBlockInterval(Header)) return;  // Interval already constructed
 
-  Interval *Int = new Interval(Header);
-  IntervalList.push_back(Int);           // Add the interval to our current set
-  IntervalMap.insert(make_pair(Header, Int));
+void Interval::print(std::ostream &o) const {
+  o << "-------------------------------------------------------------\n"
+       << "Interval Contents:\n";
 
-  // Check all of our successors to see if they are in the interval...
-  for (succ_iterator I = succ_begin(Header), E = succ_end(Header); I != E; ++I)
-    ProcessBasicBlock(Int, *I);
+  // Print out all of the basic blocks in the interval...
+  for (std::vector<BasicBlock*>::const_iterator I = Nodes.begin(),
+         E = Nodes.end(); I != E; ++I)
+    o << **I << "\n";
 
-  // Build all of the successor intervals of this interval now...
-  for(Interval::succ_iterator I = Int->Successors.begin(), 
-	E = Int->Successors.end(); I != E; ++I)
-    ProcessInterval(*I);
-}
-
-void cfg::IntervalPartition::ProcessBasicBlock(Interval *Int, BasicBlock *BB) {
-  assert(Int && "Null interval == bad!");
-  assert(BB && "Null interval == bad!");
+  o << "Interval Predecessors:\n";
+  for (std::vector<BasicBlock*>::const_iterator I = Predecessors.begin(),
+         E = Predecessors.end(); I != E; ++I)
+    o << **I << "\n";
 
-  Interval *CurInt = getBlockInterval(BB);
-  if (CurInt == Int) {                  // Already in this interval...
-    return;
-  } else if (CurInt != 0) {             // In another interval, add as successor
-    if (!Int->isSuccessor(BB))          // Add only if not already in set
-      Int->Successors.push_back(BB);
-  } else {                              // Otherwise, not in interval yet
-    for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
-      if (!Int->contains(*I)) {         // If pred not in interval, we can't be
-	if (!Int->isSuccessor(BB))      // Add only if not already in set
-	  Int->Successors.push_back(BB);
-	return;                         // See you later
-      }
-    }
-    
-    // If we get here, then all of the predecessors of BB are in the interval
-    // already.  In this case, we must add BB to the interval!
-    Int->Nodes.push_back(BB);
-    IntervalMap.insert(make_pair(BB, Int));
-    
-    if (Int->isSuccessor(BB)) {
-      // If we were in the successor list from before... remove from succ list
-      remove(Int->Successors.begin(), Int->Successors.end(), BB);
-    }
-    
-    // Now that we have discovered that BB is in the interval, perhaps some of
-    // its successors are as well?
-    for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
-      ProcessBasicBlock(Int, *I);
-  }
+  o << "Interval Successors:\n";
+  for (std::vector<BasicBlock*>::const_iterator I = Successors.begin(),
+         E = Successors.end(); I != E; ++I)
+    o << **I << "\n";
 }