-//===- 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 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/BasicBlock.h"
-#include "llvm/CFG.h"
-
-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);
-}
+#include "llvm/Analysis/Interval.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
-// 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(raw_ostream &OS) const {
+ OS << "-------------------------------------------------------------\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);
-
- // 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);
-}
+ // 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)
+ OS << **I << "\n";
-void cfg::IntervalPartition::ProcessBasicBlock(Interval *Int, BasicBlock *BB) {
- assert(Int && "Null interval == bad!");
- assert(BB && "Null interval == bad!");
+ OS << "Interval Predecessors:\n";
+ for (std::vector<BasicBlock*>::const_iterator I = Predecessors.begin(),
+ E = Predecessors.end(); I != E; ++I)
+ OS << **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);
- }
+ OS << "Interval Successors:\n";
+ for (std::vector<BasicBlock*>::const_iterator I = Successors.begin(),
+ E = Successors.end(); I != E; ++I)
+ OS << **I << "\n";
}